McLaren's masterpiece (Q1106015)

The problem addressed in this paper can be described as follows: Given an array \(b[0..n-1]\) and a permutation of \((0,1,...,n-1)\) given by an array \(H[0..n-1],\) rearrange b according to this permutation, that is, execute the multiple assignment \[ b[0],\;b[1],\;...,\;b[n-1] := b[H[0]],\;b[H[1]],\;...,\;b[H[n-1]]. \] The paper gives a new and formal description of an in-situ linear time algorithm due to Donald McLaren. For this algorithm H is encoded as a ``linked list'' represented by a variable p and an array \(c[0..n-1]\) such that \[ \begin{aligned} H[0] &= p, \\ H[1] &= c[p], \\ H[2] &= c[c[p]], \text{ etc.} \end{aligned} \] The description of the algorithm given in the paper first explores changes of H that can be performed easily by manipulating its representation using p and c.