Sorting Algorithms · Non-Comparison Sorting

Bucket Sort

Bucket sort distributes values into ranges, sorts within buckets, and concatenates the results.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

This topic teaches students that algorithm performance can depend heavily on data distribution.

Guided Lesson Notes

Understanding Bucket Sort

Bucket Sort focuses on ordering data so later operations become simpler, faster, or easier to prove correct. Bucket sort distributes values into ranges, sorts within buckets, and concatenates the results.

The mental model is this: view the array as unsorted, partially sorted, and final regions; the algorithm is the rule for growing the final order. That picture matters because it tells the student what information is available immediately and what must be searched, stored, or recomputed.

The core invariant is that after each pass or recursive call, a known part of the data must be correctly ordered or correctly partitioned. If a solution cannot state that rule, the code may still run on a sample input but fail on edge cases.

A strong implementation usually uses comparisons, swaps, shifts, partitions, merges, counts, buckets, or digit passes depending on the algorithm. The goal is not just to memorize an API; the goal is to know why each operation is allowed and what it costs.

In competitive programming, Bucket Sort tends to appear when the problem becomes easier after values are ordered, grouped, compared with neighbors, or processed by rank. Spotting that signal is often the difference between a nested-loop solution and an efficient one.

Visual Model

A small picture for Bucket Sort

Key Ideas

Bucket design
Distribution assumptions
Within-bucket sorting

Practice Prompts

Choose buckets for decimal values between 0 and 1.
Discuss what happens when values cluster in one bucket.

Vocabulary

Terms students should be able to say clearly

Comparison sort

A sorting method that learns order by comparing pairs of items.

Stable sort

A sort that preserves the relative order of equal keys.

Partition

Splitting values around a pivot or rule.

Merge

Combining sorted parts into a larger sorted result.

In-place

Using only a small amount of extra storage.

Distribution

How values are spread across the input range.

Worked Example

Worked example: tracing Bucket Sort

Use a tiny input and focus on bucket design. The goal is to see how the topic changes state before scaling it to a full problem.

1Write a small input where Bucket Sort is clearly useful.
2Label the part of the input related to Bucket design.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Simple comparison sorts	O(n^2)	Selection, insertion, and bubble sort compare many pairs on larger inputs.
Divide-and-conquer sorts	O(n log n)	Merge sort and average quicksort reduce the problem by splitting.
Non-comparison sorts	O(n + k)	Counting-style methods can be faster when the value range is controlled.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Bucket Sort interview problem: Merge Overlapping Intervals

Interview medium

Problem

Given a list of intervals, merge all overlapping intervals and print the condensed list.

Input

The first line contains n. The next n lines contain start and end values.

Output

Print the number of merged intervals, followed by one interval per line.

Sample Input

Sample Output

Why the sample works

Intervals [1, 3] and [2, 6] overlap, so they become [1, 6].

Approach

1Sort intervals by starting point.
2Keep the current merged interval.
3If the next interval starts before the current end, extend the end.
4Otherwise save the current interval and start a new one.

O(n log n) time and O(n) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] intervals = new int[n][2];
    for (int i = 0; i < n; i++) {
      intervals[i][0] = sc.nextInt();
      intervals[i][1] = sc.nextInt();
    }

    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> merged = new ArrayList<>();

    for (int[] interval : intervals) {
      if (merged.isEmpty() || interval[0] > merged.get(merged.size() - 1)[1]) {
        merged.add(interval);
      } else {
        int[] last = merged.get(merged.size() - 1);
        last[1] = Math.max(last[1], interval[1]);
      }
    }

    System.out.println(merged.size());
    for (int[] interval : merged) {
      System.out.println(interval[0] + " " + interval[1]);
    }
  }
}

Python Solution

n = int(input())
intervals = [tuple(map(int, input().split())) for _ in range(n)]
intervals.sort()

merged = []
for start, end in intervals:
    if not merged or start > merged[-1][1]:
        merged.append([start, end])
    else:
        merged[-1][1] = max(merged[-1][1], end)

print(len(merged))
for start, end in merged:
    print(start, end)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Bucket Sort: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free Consultation Text Us Open Online Compiler