Different Sorting Orders - divide and conquer?

Question

I'm trying to re-arrange a list of objects in different ways. Here I'll use integers but could be anything in this list.

The example code below sorts 1,2,3,4,5,6,7,8 into the following order: 1,8,2,7,3,6,4,5

So first. last. second. Second to last etc. It may be a bit clunky but it works.

Now what I'm trying to do now is to output the list in another order, so that it keeps dividing in two. I think this may be called Divide and Conquer but after trying / looking at some recursive sorting code etc. I'm not too clear on how to implement that here.

I hope to get the numbers ordered like this.

1,8,4,2,6,3,5,7

First, last, halfway, 1st half halfway, 2nd half halfway etc.

So in other words what I'm trying to do is to split the set of numbers in half... Then for each half in turn split those in half. And so on:

1 2 3 4 5 6 7 8
1                      (first item)
              8        (last item)
      4                (mid item)
  2                     (mid of first half) 
          6              (mid of second half)
    3                    (mid of 1st chunk)
        5                (mid of 2nd chunk)
           7             (mid of 3rd chunk)

If anyone could anyone show me how to do this, with this simple example, that'd be really great.

 static void Main(string[] args)
    {

        List<int> numberlist = new List<int>();

        numberlist.Add(1);
        numberlist.Add(2);
        numberlist.Add(3);
        numberlist.Add(4);
        numberlist.Add(5);
        numberlist.Add(6);
        numberlist.Add(7);
        numberlist.Add(8);

        int rev = numberlist.Count-1;
        int fwd = 0;

        // order 1,8,2,7,3,6,4,5

        for (int re = 0; re < numberlist.Count; re++)
        {
            if (re % 2 == 0)
            {
                Console.WriteLine(numberlist[fwd]);
                fwd++;                       
            }
            else
            {
                Console.WriteLine(numberlist[rev]);
                rev--;
            }
        }
        Console.ReadLine();
    }

Some more sample ranges and output, to be read left-to-right, top-to-bottom:

1 2 3 4 5 6 7
1           7
      4
  2     5
    3     6

1 2 3 4 5 6 7 8 9 10 11 12
1                       12
          6 
    3           9 
  2   4     7     10
        5     8      11


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1                                   16
              8 
      4                 12
  2       6       10          14
    3   5   7   9    11    13    15

Answer 1

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.