Bucket Sort
Learn Bucket Sort (Sorting, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Bucket Sort - Average O(n + k), Best for Uniform Distributions Distributes elements into several "buckets" by value range, sorts each bucket individually (typically with insertion sort, since buckets are small), then concatenates the buckets in order. Works best when input is UNIFORMLY distributed over a known range - the same assumption interpolation search relies on.