Different Sorting Orders - divide and conquer?

Let me see if I understand the problem. Let's work an example with more items:

This is the order you want?

ABCDEFGHIJKLMNOPQ
A               Q  
        I
    E       M
  C   G   K   O
 B D F H J L N P

That seems straightforward. Create a data structure called "Interval" that has two fields: the Greatest Lower Bound and the Least Upper Bound. That is, what are the elements that are the biggest thing that is below the interval and the smallest thing that is above the interval. The algorithm goes like this:

Input: the size of the array.
Yield the first item -- if there is one
Yield the last item -- if it is different from the first item.
Make a queue of intervals.
Enqueue the interval (0, array.Length - 1) 
While the queue is not empty:
    Dequeue the queue to obtain the current item.
    Is the interval empty? If so, skip this interval
    Otherwise, the interval has a GLB, a LUB, and a value in the middle.
    Yield the middle of the interval
    Enqueue the interval (bottom, middle)
    Enqueue the interval (middle, top)

Let's work the example above. We have the array ABCDEFGHIJKLMNOPQ.

Yield A
Yield Q
Enqueue A-Q. The queue is now A-Q
Is the queue empty? No.
Dequeue the queue. It is now empty.
current is A-Q
Is the current interval empty? no.
The middle is I.
Yield I.
Enqueue A-I. The queue is now A-I.
Enqueue I-Q. The queue is now A-I, I-Q.
Is the queue empty? No.
Dequeue the queue. It is now I-Q.
current is A-I.
Is the current interval empty? No.
The middle is E.
Yield E.
Enqueue A-E. The queue is now I-Q, A-E.
Enqueue E-I. The queue is now I-Q, A-E, E-I
Is the queue empty? No.
Dequeue. The queue is now A-E, E-I
current is I-Q
The middle is M
Yield M.
Enqueue I-M
Enqueue M-Q.  The queue is now A-E, E-I, I-M, M-Q
OK, let's start skipping some steps here. The state of the queue and the yields are:
Yield C
E-I, I-M, M-Q, A-C, C-E
Yield G
I-M, M-Q, A-C, C-E, E-G, G-I
Yield K
M-Q, A-C, C-E, E-G, G-I, I-K, K-M
yield O
A-C, C-E, E-G, G-I, I-K, K-M, M-O, O-Q
yield B
C-E, E-G, G-I, I-K, K-M, M-O, O-Q, A-B, B-C
OK, skip more steps...
Yield D, F, H, J, L, N, P
Queue is now A-B, B-C, C-D, D-E, ... P-Q
Every interval is now empty, so we skip all of htem and we are done.

Make sense?

The trick here is to notice that the order you want is a breadth-first visit of a tree. You just have to be able to "see through" the array to the tree structure that you want to traverse.

Incidentally, the ordering seems a bit weird. The ordering for the most part seems to be "divide the range into two parts and yield the middle of each range first". Why then are the two extremes yielded first, instead of last? I would find the ordering:

ABCDEFGHIJKLMNOPQ
        I
    E       M
  C   G   K   O
 B D F H J L N P
A               Q  

more intuitively obvious; if the things "in the middle" always get priority over things "at the extremes" then the extremes should go last, not first.

I can demonstrate a similar selection; it results in a slightly different order to yours.

Take the numbers 0 to 7, and express them in binary: 000 001 010 011 100 101 110 111.

Now, reverse them: 000 100 010 110 001 101 011 111.

In decimal, this gives 0 4 2 6 1 3 5 7. So you start with the first element, then halfway through the rest of the elements, then a quarter and three quarters, and then finally all the odd-numbered elements.

Obviously this procedure only works for exact powers of two.