The Array-Based Bucket Sort Algorithm

Classical bucket sort algorithm implements buckets as dynamic lists. It sorts uniform data efficiently within O(N) time but degrades to the inefficient O(N\+2) insertion sort when handling extremely-nonuniform data. By analyzing counting sort with extra data, a method is presented to implement the buckets as sequential arrays. The efficiency is improved directly by avoiding the complex operations of dynamic memory allocation. Furthermore, O(N log N) algorithms like quicksort may be employed to manage each bucket. The composed algorithm still sorts uniform data within O(N) time but simply degrades to the original O(N log N) algorithm in the worst case. In general case, it is proved that the composed bucket sort algorithm always achieves better performance. Experiments on uniform data show the superiorities of the bucket sort algorithms, and that the array-based bucket sort algorithm beats the classical algorithm. In experiments with Gaussian data, the non-uniformity influences the array-based algorithm much less than the classical algorithm where both outperform the quicksort.