Suppose you are given an unsorted list of positive integers, and you wish to order them in a manner such that the elements alternate as: (less than preceding element), (greater than preceding element), (less than preceding element), etc... The very first element in the output list may ignore the rule. So for example, suppose your list was: 1,4,9,2,7,5,3,8,6.
One correct output would be... 1,9,2,8,3,7,4,6,5
Another would be... 3,4,2,7,5,6,1,9,8
Assume that the list contains no duplicates, is arbitrarily large, and is not already sorted.
What is the most processing efficient algorithm to achieve this?
Now, the standard approach would be to simply sort the list in ascending order first, and then peel elements from the ends of the list in alternation. However, I'd like to know: Is there a more time-efficient way to do this without first sorting the list?
My reason for asking: (read this only if you care)
Apparently this is a question my sister's boyfriend poses to people at job interviews out in San Francisco. My sister asked me the question, and I immediately came up with the standard response. That's what everyone answers. However, apparently one girl came up with a completely different solution that does not require sorting the list, and it appears to work. My sister couldn't explain to me this solution, but the idea has been confounding me since last night. I'd appreciate any help! Thanks!