I believe that the author is referring to the case when the array to be sorted contains only duplicates of a small number of items, where a perfect hash function can speed up insertion; this turns cycle sort's time complexity into Θ(n+k), with <i>k</i> being the number of hashes. In such a case, <i>k</i> is not negligible compared to <i>n</i>, so I wouldn't feel comfortable saying cycle sort is O(n), as he does.<p>In the general case, cycle sort is Θ(n^2) with a total space complexity of Θ(n).<p>edit:typos.
If you must restrict the input to permutations of [0,...,N], you already know the result! Finding cycles is neat, but this works for the same data, minus having bounds:<p>(define (trivialsort vals) (lambda (i) i))
It's nice to say this algorithm is virtually O(n) in practice, but that's about the "cycling" mechanism only. It needs to prepare a dictionary with offsets, which has to loop over all the keys, perform an O (log n) insert operation on all the keys, and allocate memory on the heap. This already makes it (almost) O (n log n), without even doing the actual sorting.<p>It's a nice idea, but it's not O(n).