sorted by hash, counting the number of occurrences of each hash in the array. Then create a table with the cumulative sum of each entry in the histogram. The cumulative sum table will then contain the position in the array of each element. The proper place of elements can then be found by a constant-time hashing and cumulative sum table lookup rather than a linear search. References External links "Cycle-Sort: A Linear Sorting Method", The Computer Journal (1990) 33 (4): 365-367. Original source of unrestricted variant Cyclesort - a curious little sorting algorithm Sorting algorithms Comparison sorts Articles with example pseudocode Articles with example Python (programming language) code Articles with example C++ code