algorithm - Interleave three equally sized partitions in an array inplace in O(n) time

Question

Given an array of size 3n of the form

[x1, x2, x3... xn, y1, y2, y3... yn, z1, z2, z3... zn]

Convert it to [x1, y1, z1, x2, y2, z2, ... xn, yn, zn]

Here xn, yn, zn can be any integers. See example input and output below.

Two constraints

1. Do in O(n)
2. O(1) memory (inplace)

An example input and output are as follows.

Input :
[5, 8, 11, 3, 2, 17, 21, 1, 9] 3n = 9. So n = 3.

Here x1=5 x2=8 x3=11 y1=3 y2=2 y3=17 z1=21 z2=1 z3=9

Output :
[5, 3, 21, 8, 2, 1, 11, 17, 9]

One possible O(n log n) soln: Considering just x's and y's. Now I can swap all y's to its position which will leave me x2, x4, x6 swapped out of position. Then I will swap in x2, x4's which will leave x3, x7's out of position. And next iteration would be x8, x16's. This would take me to O(n log n) but not O(n).

Answer 1

This answer is based on work by Peiyush Jain (whose bibliography is woefully incomplete, but I don't feel like taking the time to straighten out the history of the in-place transposition problem). Observe that 3 is a primitive root of 25 = 5^2, since

>>> len(set(pow(3,n,25)for n in range(25)))
20

and 20 is Euler's totient of 25. By Jain's Theorem 1, a classic result in number theory, 3 is a primitive root for all 5^k.

When the array has length 3n, the new position of the element at position k*n + j is 3*j + k. In general, the new position of i (except for the last element) is (i*n) % (3*n - 1). Note that n is the multiplicative inverse of 3 modulo 3*n - 1, so 3 is a primitive root if and only if n is.

Jain's observation, in this case, is that, if 3*n - 1 is a power of 5, then the permutation above has log_5 (3*n - 1) + 1 distinct cycles, led by 5^k for k from 0 to log_5 (3*n - 1). (This is more or less the definition of primitive root.) For each cycle, all we have to do is move the leader, move the element displaced by the leader, move the element displaced by the element displaced by the leader, etc., until we return to the leader.

For other array sizes, break the array into O(log n) implicit subarrays of lengths 3 and one plus powers of 5 that are divisible by 3: 6, 126, 3126, 78126, etc. Do a series of rotations, decreasing geometrically in size, to get the subarrays contiguous, then run the above algorithm.

If you actually implement this, please benchmark it. I did for the base case of Jain's algorithm (3^n - 1, pairs instead of triples) and found that, on my machine the O(n log n)-time algorithm was faster for non-galactic input sizes. YMMV of course.