If A is an array with the following elements: $$ a_1,a_2,...,a_n,b_1,b_2,...,b_n $$
How to shuffle A to form: $$ a_1,b_1,a_2,b_2,...,a_n,b_n $$
with minimal swaps and using no additional space?
I read this answer and wrote the following code:
def shuffle(a,left,right): if right - left>=4: half = (right - left)/2 for i in xrange(half/2): tmp = a[left + half + i] a[left + half+i] = a[left + half/2 + i] a[left + half/2 + i] = tmp shuffle(a,left,left + (right - left)/2) shuffle(a,left + (right - left)/2, right) a = ['a1','a2','a3','a4', 'b1','b2','b3','b4'] shuffle(a,0,len(a))
This gives an algorithm with O(nLog(n)) swaps. But I realized that this works only when n = 2k for some integer k. Is there a minor tweak that one could make to get the same complexity for arbitrary n?