# Interleaving first and second half of an array of even length in place

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?

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?

• Can you discover something about the cycles that for with that permutation for various $n$? Jun 30, 2017 at 15:47
• I didn't quite catch you - "that for with that permutation"? Jun 30, 2017 at 17:17
• $a2$ moves to index 3 which replaces $a3$ which moves to index 5 which replaces $a5$ which moves to index 9, eventually that will loop back to index 2. That's a cycle, Investigate how the cycles evolve as n increases. Jun 30, 2017 at 17:54
• Consider the permutation $\sigma: \{1,2,\dots,2n\} \to \{1,2,\dots,2n\}$ that you're trying to implement, i.e., $\sigma(i)=2i-1$ for $i\le n$ and $\sigma(i)= 2(i-n)$ for $i>n$. Can you characterize its cycle structure? How many cycles does it have of each possible length? Then use the fact that you can permute a cycle of length $\ell$ using $\ell-1$ swaps, and sum over all the cycles. See cs.stackexchange.com/q/71154/755.
– D.W.
Jun 30, 2017 at 19:25
• That link already describes how to handle the case of arbitrary $n$. I'm not sure what your question is, exactly -- it seems like it is already answered by the answers over there.
– D.W.
Jun 30, 2017 at 19:34