Linear-Time Sorts

Bucket Sort

Distribute elements into buckets based on their value range. Sort each bucket individually (small buckets can use insertion sort). Concatenate buckets. Works best when data is uniformly distributed.

O(n + k) avg

O(n + k)

How It Works

Bucket sort distributes elements into b buckets by a simple value-to-bucket mapping — typically floor(value * b / range) — so bucket boundaries partition the value space. Each bucket is then sorted independently (insertion sort is customary since buckets should be small), and the buckets are concatenated in order. The mapping guarantees everything in bucket i precedes everything in bucket i+1, so no cross-bucket merging is needed.

When input values are roughly uniformly distributed, each of n buckets holds O(1) elements in expectation, and total expected time is O(n). Skewed data breaks that assumption — one overloaded bucket degrades toward the inner sort's O(n^2). The bucketing idea also solves problems beyond sorting: Maximum Gap bounds the answer using the pigeonhole principle across buckets, and Top K Frequent Elements buckets by frequency count.

Step-by-Step Visualization

Distribute into buckets by range

Buckets30s: [32,33,37] | 40s: [42,47] | 50s: [52,51]

1/3

Code

Java

static int[] bucketSort(int[] arr) {
  int n = arr.length;
  int max = 0;
  for (int x : arr) max = Math.max(max, x);
  List<List<Integer>> buckets = new ArrayList<>();
  for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());

  for (int num : arr) {
    int idx = (int)((long)num * n / (max + 1));
    buckets.get(idx).add(num);
  }

  for (List<Integer> bucket : buckets) Collections.sort(bucket);
  List<Integer> result = new ArrayList<>();
  for (List<Integer> bucket : buckets) result.addAll(bucket);
  return result.stream().mapToInt(Integer::intValue).toArray();
}

Tips & Gotchas

1Distribute elements into k buckets based on value range

2Sort each bucket individually (insertion sort works for small buckets)

3Concatenate all buckets

Practice Problems

1Maximum Gap
2Top K Frequent Elements
3Contains Duplicate III
4Sort Characters By Frequency

About the Linear-Time Sorts Pattern

These bypass the O(n log n) barrier by NOT comparing elements. Instead, they use the values directly. The catch: they only work when values fall within a known, bounded range.

Key insight

Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.

Common Sorting Interview Problems

Sort Colors
Kth Largest Element
Merge Intervals
Largest Number
Sort List
Meeting Rooms

Frequently Asked Questions

What distinguishes bucket sort from counting sort?

Counting sort needs one counter per distinct value and only tallies exact occurrences, restricting it to small integer ranges. Bucket sort maps ranges of values — including floats — to each bucket and sorts within buckets, so it handles continuous data at the cost of depending on distribution uniformity for its linear expected time.

How does Maximum Gap use buckets to reach O(n) time?

With n values spanning [min, max], the pigeonhole principle guarantees some adjacent sorted pair differs by at least (max-min)/(n-1); making each bucket slightly narrower than that bound forces the maximum gap to occur between buckets, not inside one. Tracking only each bucket's min and max and scanning adjacent non-empty buckets then finds the answer without sorting.

What happens when the data is heavily skewed?

Most elements land in a few buckets, so the per-bucket insertion sort degrades toward O(n^2). Remedies include using an O(n log n) sort inside buckets to cap the damage, choosing bucket boundaries from sampled quantiles rather than uniform ranges, or preferring radix sort for adversarial integer data.