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 functio

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.