LearnViz CompSci
Home / Learn / Algorithms / Bucket Sort

Intermediate Topic 20 of 51 Algorithms

Bucket Sort

Distributing values into ranges then sorting each bucket.

How it works

Bucket sort distributes the elements into a number of buckets according to their value range, sorts each bucket individually, often with insertion sort, and concatenates the buckets. When input is uniformly distributed, each bucket holds few items and the expected running time is O(n + k). It is a distribution sort that avoids comparing across buckets.

Where it is used

Sorting floating-point numbers in a known range such as 0 to 1, histogram-based processing, sorting by user ratings or scores and parallel sorting where buckets map to workers use bucket sort.

Common pitfall

Skewed data puts most elements into one bucket and degrades to the cost of the inner sort, up to O(n squared). The bucket mapping must be monotonic to keep order. Choosing the number of buckets is a trade-off with memory. The stability of the final result depends on the inner sort.

Where it fits in the course

Bucket Sort is topic 20 of 51 in Algorithms, rated Intermediate. It follows Shell Sort. The next topic is Timsort.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Algorithms quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Bucket Sort?
Distributing values into ranges then sorting each bucket. It belongs to Algorithms and is an intermediate-level topic.
Where do people use Bucket Sort?
Sorting floating-point numbers in a known range such as 0 to 1, histogram-based processing, sorting by user ratings or scores and parallel sorting where buckets map to workers use bucket sort.
What is the most common mistake with Bucket Sort?
Skewed data puts most elements into one bucket and degrades to the cost of the inner sort, up to O(n squared).
What should I learn before this topic?
Start with Shell Sort, the topic just before it in Algorithms.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Algorithms quiz. You can also explore Sorting Algorithms in the Visual Lab.
Is Bucket Sort hard to learn?
It is an Intermediate topic. Be comfortable with the Beginner topics in this area first, then read the common pitfall carefully, since it is where most mistakes happen.
How long does it take to learn Bucket Sort?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Bucket Sort?
Shell Sort, Timsort, Heap Sort are closely connected. The full list is in the related topics section of this page.
What should I study after Bucket Sort?
Continue with Timsort, the next topic in Algorithms.

Related topics