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 k being the number of hashes. In such a case, k is not negligible compared to n, so I wouldn't feel comfortable saying cycle sort is O(n), as he does.

In the general case, cycle sort is Θ(n^2) with a total space complexity of Θ(n).

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:

(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.

It's a nice idea, but it's not O(n).

Nice use of Slovenia's TLD.

I wonder how it sounds ;)