Course contentsShow
← Computer Science
Lesson 795 of 2,87218. Sorting AlgorithmsFree lesson

Bucket Sort: Partitioning the Range

Distributing elements into buckets based on value ranges to sort in average linear time.

Bucket Sort: Partitioning the Range

What you'll learn: How bucket sort distributes elements into separate "buckets" based on their value ranges to achieve fast sorting under the right conditions.


The Core Idea

Bucket sort works by dividing the input range into several intervals called buckets, distributing elements into these buckets based on their values, sorting each bucket individually, and then concatenating all buckets in order.

Think of organizing a deck of cards: instead of sorting all 52 cards at once, you first separate them into four suit piles (hearts, diamonds, clubs, spades), sort each pile, then combine them. Each suit is a "bucket."

How It Works

  1. Determine the range: Find the minimum and maximum values in your data
  2. Create buckets: Divide this range into equal-sized intervals (buckets)
  3. Distribute: Place each element into the appropriate bucket based on its value
  4. Sort buckets: Sort each bucket individually (often using insertion sort for small buckets)
  5. Concatenate: Merge all buckets back together in order

When Bucket Sort Shines

Bucket sort achieves average-case O(n) time when:

  • Input is uniformly distributed across the range
  • You use an appropriate number of buckets (often n buckets for n elements)
  • Elements spread evenly, so each bucket stays small

If all elements land in one bucket, performance degrades to whatever algorithm you use to sort that bucket—potentially O(n²).

Practical Example

Sorting student grades (0-100): create 10 buckets for ranges [0-9], [10-19], ..., [90-100]. A grade of 87 goes into bucket 8, a grade of 42 into bucket 4. Sort each bucket, then concatenate.

Key Takeaway: Bucket sort partitions the input range into intervals, distributing elements accordingly to achieve linear average-case time when data is uniformly distributed.