How to output a permutation of B such that A is a wiggly?

Question

I was faced with the following question:

Given an unsorted array B[1 . . 2n+1] of real numbers, give a linear time algorithm that outputs a permutation A[1..2n+1] of B such that A is a wiggly.

I basically did a merge sort and altered it:

 MergeSort(a,n)
      int i=2;
     while (i ≤ n)
     {
       Swap(a[i−1], a[i]);
       i=i+2;
     }

But the time complexity is O(nlogn) + O(n) (from sorting and from the loop, respectively), which yields O(nlogn). But I want to do it in O(n) time.

Should I use counting sort / radix sort / bucket sort to get a linear time and then alter it to get a wiggly array?

Answer 1

There is a simple linear solution:

for i = 2 ... 2 * n - 1:
     if i % 2 == 0 and a[i] < a[i - 1] or i % 2 == 1 and a[i] > a[i - 1]:
         swap(a[i], a[i - 1])

Proof of correctness:

Let's use induction:

1. Base case: only one element is processed, no constraints are violated.

2. Step: if i % 2 == 0: If we do not swap anything at this step, the prefix remains valid. Otherwise, we have the following situation: a[i - 2] >= a[i - 1] > a[i]. When we make a swap, we can see that the constraints are not violated for the i - 2 and i - 1 elements, and the last position is fixed. For an odd i, the situation is similar.