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

algorithm, arrays, sorting

Solution

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:

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

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.

Problem

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?

Original source