Sorting in linear time - variations on the bucket sort
Edward M. Corwin, Antonette M. Logar · Journal of computing sciences in colleges · 2004
The Bucket Sort is an algorithm for sorting in linear time. That is, we can sort a list of n numbers in expected time O(n). Implementing the Bucket Sort shows off several important aspects of data structures and operating systems in some surprising ways. Implementation details will be discussed leading to faster variations that are not obvious.