Solution To "An Unusual Sorting Algorithm"

View Problem: An Unusual Sorting Algorithm

It is easy to see that the position of the number x in the final sorted array should be x. It it also clear form the algorithm that the operation for every i is essentially swap(i, A[i]), meaning swap the numbers at indices i and A[i]. This means, the value at A[i] eventually becomes A[i]. So, in one iteration of the while-loop, for all i in [1..N], we attempt to correctly place A[i] in it's correct position which is A[i]. Let us look at an example:

A = {4,3,1,2}

1st iteration -

i=1: swap(1,A[1]) = swap(1,4). So, A = {2,3,1,4} // Correctly placing 4
i=2: swap(2,A[2]) = swap(2,3). So, A = {2,1,3,4} // Correctly placing 3
i=3: swap(3,A[3]) = swap(3,3). So, A = {2,1,3,4} // Correctly placing 3
i=4: swap(4,A[4]) = swap(4,4). So, A = {2,1,3,4} // Correctly placing 4 

2nd iteration -

i=1: swap(1,A[1]) = swap(1,2). So, A = {1,2,3,4} // Correctly placing 2
i=2: swap(2,A[2]) = swap(2,2). So, A = {1,2,3,4} // Correctly placing 2
i=3: swap(3,A[3]) = swap(3,3). So, A = {1,2,3,4} // Correctly placing 3
i=4: swap(4,A[4]) = swap(4,4). So, A = {1,2,3,4} // Correctly placing 4 

The array A is now sorted.

However while placing A[i] in its correct position, we may fail to place A[A[i]] in its correct position, as, clearly, placing A[A[i]] at i does not guarantee that it has been placed correctly. This can be noticed in the above example. When we perform swap(1,4) in the 1st iteration, we place 4 at position 4 but we place 2 at position 1.

At every i, we place one element correctly in its position. However, we may be trying to place an already correctly placed element in the same position. This can be observed at i=3 and i=4 in the 1st iteration of our example. Hence, clearly, we may need more than one iterations for sorting array A.

With this insight, let us now try to derive a worst-case complexity for sorting array A. Let us represent array A with R's and W's. An 'R' at position i means the element at this position is "Rightly" placed. A 'W' at position i means the element at this position is "Wrongly" placed.

A = {4,3,1,2} // {W,W,W,W}

1st iteration -

i=1: swap(1,A[1]) = swap(1,4). So, A = {2,3,1,4} // {W,W,W,R}
i=2: swap(2,A[2]) = swap(2,3). So, A = {2,1,3,4} // {W,W,R,R}
i=3: swap(3,A[3]) = swap(3,3). So, A = {2,1,3,4} // {W,W,R,R}
i=4: swap(4,A[4]) = swap(4,4). So, A = {2,1,3,4} // {W,W,R,R} 

2nd iteration -

i=1: swap(1,A[1]) = swap(1,2). So, A = {1,2,3,4} // {R,R,R,R}
i=2: swap(2,A[2]) = swap(2,2). So, A = {1,2,3,4} // {R,R,R,R}
i=3: swap(3,A[3]) = swap(3,3). So, A = {1,2,3,4} // {R,R,R,R}
i=4: swap(4,A[4]) = swap(4,4). So, A = {1,2,3,4} // {R,R,R,R} 

The array A is now sorted.

Clearly, swapping two W's replaces at least one of these two W's with R. Also, if we come across an R, it makes no difference (and hence no value-addition towards sorting) at all.

Our goal is to convert array A from N W's to N R's. Since two W's in the worst case produce one R in a single iteration, half of the wrongly placed array gets rightly placed. Hence, we can now say that the while-loop runs at most O(logN) number of times. So, the complexity of our algorithm is O(NlogN).

To create an array which gets only half sorted in every iteration, we use the following strategy. We try to ensure that all the R's get created at the right-end of the array, and, exactly half the W's get converted to R's. So, an ideal array A for N = 2 will be A = {2,1} so that it takes at least one iteration to sort it. For N=4, we have to ensure that it takes 2 iterations. Since our original array for N = 2 is {2,1}, our desired array A at the end of 1st iteration for N = 4 should be A = {2,1,3,4}. This would mean our original array A to be A = {4,3,1,2}.

After applying this strategy, let us create an array for N = 8. Since our original array for N = 4 is {4,3,1,2}, we would like our desired array for N = 8 at the end of 1st iteration to be A = {4,3,1,2,5,6,7,8}. To find our original array for N = 8, we let the first half be {8,7,6,5} and the second half to be Invert(Original array for N=4), so that the desired array plays out for us as intended. Hence, for N = 8, original array A = {8,7,6,5,2,1,3,4}. A similar strategy can be applied for any general N.