Code: Select all

`[a_1, a_2, ..., a_n, b_1, b_2, ..., b_n]`

Code: Select all

`[a_1, b_1, a_2, b_2, ..., a_n, b_n]`

The data in the array is arbitrary. In other words, after you move elements around, you cannot recognize that an element is, say, a_3 without using space to keep track of that.

My friend, over the phone, gave an algorithm* that required O(n*log(n)) time. Can anyone think of a O(n) algorithm? (Or, if perhaps the interviewers are devious, prove the problem requires ω(n) time?)

*His algorithm is swap the array to

Code: Select all

`[a_1, b_1, a_3, b_3, ..., a_{n-1}, b_{n-1}, a_2, b_2, a_4, b_4, ..., a_n, b_n]`