Initially there is a sorted array. Say, Initially array A was

```
A= 0 0 1 2 5 6 8 8 9 10
i= 0 1 2 3 4 5 6 7 8 9
```

Following 3 operations are performed to obtain B from A

- Copy elements in even indices from A to B
- Split odd indices into two parts
`left`

and`right`

. If there are odd number of odd indices ignore middle most odd number when computing`left`

and`right`

so that both have same number of odd numbers. - For every odd index in
`left`

, swap it with some odd index in`right`

.

For example, B can be

```
B= 0 10 1 8 5 |6| 8 2 9 0
i= 0 1 2 3 4 |5| 6 7 8 9
```

(|| used to show left and right)

`B`

could also be

```
B= 0 8 1 10 5 |6| 8 0 9 2
i= 0 1 2 3 4 |5| 6 7 8 9
```

Search in this array B for key k.

Another simpler example,

```
A= 0 1 2 3 4 |5| 6 7 8 9
i= 0 1 2 3 4 |5| 6 7 8 9
```

`B`

can be

```
B= 0 7 2 9 4 |5| 6 1 8 3
i= 0 1 2 3 4 |5| 6 7 8 9
```

or

```
A= 0 9 2 7 4 |5| 6 3 8 1
i= 0 1 2 3 4 |5| 6 7 8 9
```