An Internal Hybrid Sort Algorithm Revisited
Olli Nevalainen, Timo Raita · The Computer Journal · 1992
Two hybrid methods of distributive sort and quicksort are given. The first method sorts an array of records and the second one sorts a linearly linked list in a stable way. The expected running time of the methods is O(n) for n records and for a wide class of distributions of the keys (including all bounded densities with a compact support). For most other distributions the running time is O(n log n), and the worst case time is O(n2). The array version needs extra storage space for n records and approximately n/5 integers. In the linked list version only an array of n/5 pointers is needed. The observed running times of the algorithms compare favourably with those of other efficient bucket sort algorithms.