Sorting by hashing and inserting
Govind Gupta · Proceedings of the 17th conference on ACM Annual Computer Science Conference · 1989
Address calculation sorting method is discussed by Kronmal & Tartar (Proc. ACM Nat'l Conf 21). Generally collision resolution is done by chaining, where the records are inserted in ordered linked lists with heads defined as array of pointers. Then the linked lists are merged in the original array. For uniformly distributed lists and careful choice of a hash function the algorithm works quite efficiently and is faster than other sorting methods. Our comparisons show that the algorithm works more than twice as fast as Quick Sort. The disadvantage with this method is that it needs extra space for 2N records. Also it is not an in place sort.