Given an array, a, of unsorted distinct integers, arrange them so that a[0] < a[1] > a[2] < a[3] > a[4], etc.

So, given the array [3, 1, 7, 5, 9], one possible solution is [1, 7, 3, 9, 5].

One way to do this would be to sort the array and then take the last part, starting from the end of the array, and interleave it with the first. So, for example:

    [3, 1, 7, 5, 9]  // original array
    [1, 3, 5, 7, 9]  // sorted
    [1, 9, 3, 7, 5]  // rearranged into another possible solution

That’s kind of expensive, though. It takes O(n log n) to sort. It would take O(n) to build the rearranged list into a new array. O(n²) to rearrange in place naively. Perhaps you could do an in-place rearrangement in O(n log n).

There’s a faster solution that takes O(n) to rearrange the numbers. Believe it or not, it’s as simple as scanning the array, checking each pair of numbers to see if they meet the condition (a[i] < a[i+1] for the even pairs, and a[i] > a[i+1] for the odd pairs). If a pair doesn’t meet the condition, swap them. Expressed in code, it looks like this:

    for i = 0 to n-2
        if i is even
            // ensure a[i] < a[i+1]
            if (a[i] > a[i+1])
                swap(a[i], a[i+1])
            end if
        else
            // ensure a[i] > a[i+1]
            if (a[i] < a[i+1])
                swap(a[i], a[i+1])
        end

Really, that’s all there is to the algorithm.

Let me explain why it works.

Given three distinct numbers, (a, b, c) there are four possible relationships:

1. a < b < c
   The first condition is met. We know that a < c, so if we swap b and c, we end up with a < c > b
2. a < b > c
   Both conditions are already met.
3. a > b < c
   Here we have to swap a and b to give b < a ? c. But we already know that b < c, so if a < c, swapping a and c still gives us b < c > a.
4. a > b > c
   We know that a > c, so swapping a and b to meet the first condition maintains the second condition, giving b < a > c.

Okay, so it works with three numbers. Now what happens when you add a fourth? You have a < b > c ? d. If c < d, then of course everything’s fine. If c > d, then we have case 4 above, and we already know that swapping c and d will not invalidate the first condition.

Similarly, given a < b > c < d ? e, if d > e then we move on. Otherwise we have case 1 above, which we know can be resolved by swapping, without affecting the first condition.

I just love the elegance of this solution. It’s so … neat.