bucket sort

Bucket sort is a distribution-based sorting algorithm that scatters the elements of a collection into a fixed number of ordered buckets, sorts each bucket on its own, and then concatenates the buckets back into one fully sorted sequence.

Unlike comparison sorts such as quicksort and merge sort, bucket sort never compares two arbitrary elements to decide their order. Instead, a mapping function sends each value to the bucket that covers its range, so the buckets stay ordered relative to one another.

Within a bucket, a secondary method finishes the job. Insertion sort is a common choice for the small groups that result, and a recursive bucket sort can handle data that is still spread widely.

The interactive visualization below steps through all three phases on a small list, tinting each value by the bucket it maps to. Watch for the scatter, sort, and gather labels as each phase runs.

The approach works best when the input is drawn roughly uniformly from a known interval, because the values then land in evenly filled buckets. Its behavior splits into distinct cases:

• Average case: with the elements spread evenly and the bucket count chosen near the number of items, each bucket holds only a few values, so the total work is linear, O(n).
• Worst case: when every value collides in a single bucket, the cost collapses to the O(n²) of the inner sort.
• Space: the algorithm does not sort in place and needs O(n + k) extra room for its buckets.

Bucket sort belongs to the same distribution-sorting family as radix sort and counting sort, the special case that uses one bucket per distinct key. It often sorts uniformly distributed floating-point values, where its linear average cost beats the O(n log n) lower bound that constrains any comparison-based method.

Related Resources

Tutorial

Sorting Algorithms in Python

In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.

intermediate algorithms python

For additional information on related topics, take a look at the following resources:

• Introduction to Sorting Algorithms in Python (Course)
• Recursion in Python: An Introduction (Tutorial)
• Thinking Recursively in Python (Tutorial)
• How to Do a Binary Search in Python (Tutorial)
• Creating a Binary Search in Python (Course)
• Sorting Algorithms in Python (Quiz)
• Recursion in Python (Course)
• Recursion in Python: An Introduction (Quiz)
• Thinking Recursively With Python (Course)
• Thinking Recursively in Python (Quiz)