An Unusual Sorting Algorithm

Nandu was thinking about arrays and sorting techniques, when he suddenly stumbled upon a sorting algorithm for a permutation of the sequence [1..N]. Extremely proud of the new technique he invented, he goes to Rani to show her his algorithm.

Assume the 1-indexed array A contains a permutation of the sequence [1..N]. We will sort this array A in ascending order in the following manner:

while(!issorted(A))
{
    for(i=1; i<=N; i++)
    {
        temp = A[i];
        A[i] = A[A[i]];
        A[A[i]] = temp;
    }
}

The issorted() function returns true only if array A is sorted, otherwise, it returns false.

However, Rani doesn't seem to be very impressed by Nandu's algorithm. She asks Nandu what would be the worst case complexity of his algorithm. She also asks for a clear proof of the worst case complexity. So, for a given N,  Nandu has to provide a permutation of the sequence [1..N] where the outer while-loop of his algorithm will be executed the maximum number of times.

Can you help Nandu with this problem?

View Solution: Solution to "An Unusual Sorting Algorithm"