Wave Sorting
March 4, 2016
A list of integers is sorted in “wave” order if alternate items are greater than their immediate neighbors (thus the other alternate items are less than their immediate neighbors). Thus, the list [4 1 7 5 6 2 3] is in wave order because 4 > 1, then 1 < 7, then 7 > 5, then 5 < 6, then 6 > 2, and finally 2 < 3. Note that the two alternate streams [4 7 6 3] and [1 5 2] need not themselves be sorted. It doesn’t matter if the first item is the high wave or the low trough between waves, though starting with a wave is traditional.
Your task is to write a program that takes a list of unique integers and sorts it into wave order. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
What about sorting the given integers, and then swapping ith element with (n-i)th element. It will solve the repeated integer problem for most of the cases.
That’s what I was thinking – sort lowest to highest in a temporary array, then return the largest, then smallest, then second-largest, then second-smallest, etc – so the same result with more or less the same method.
The problem comes if the last few numbers to be processed (ie the middle numbers in the highest-to-lowest temporary array) contain duplicates…
…I haven’t thought of a bullet-proof algorithm yet.
[…] have written a function to perform wave-sort as shown below. The resulting array should begin with a number bigger than the next one but my code […]