Bucket sort is a distribution-based sorting algorithm. Instead of comparing elements, it spreads them into "buckets" based on their value, sorts each bucket individually, then concatenates the results. When data is uniformly distributed, it achieves average O(n) time — faster than comparison-based sorts which are bounded by O(n log n).

How Bucket Sort Works

1. Find the minimum and maximum values in the input
2. Create k empty buckets covering the value range
3. Distribute each element into its appropriate bucket
4. Sort each bucket individually
5. Concatenate all buckets in order to produce the sorted output

Visual Walkthrough

Input: [42, 13, 75, 29, 88, 5, 61, 37] — min=5, max=88, 4 buckets

Range per bucket = (88 - 5 + 1) / 4 ≈ 21

Bucket 0 [5–25]:   [13, 5]      → sorted: [5, 13]
Bucket 1 [26–46]:  [42, 29, 37] → sorted: [29, 37, 42]
Bucket 2 [47–67]:  [61]         → sorted: [61]
Bucket 3 [68–88]:  [75, 88]     → sorted: [75, 88]

Final result: [5, 13, 29, 37, 42, 61, 75, 88] ✓

Java Implementation

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BucketSort {

    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int min = arr[0], max = arr[0];
        for (int val : arr) {
            if (val < min) min = val;
            if (val > max) max = val;
        }

        if (min == max) return; // all values are equal

        int bucketCount = arr.length;
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        double divisor = (double)(max - min + 1) / bucketCount;
        for (int val : arr) {
            int bucketIndex = (int)((val - min) / divisor);
            // Clamp to avoid floating-point edge cases
            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
            buckets.get(bucketIndex).add(val);
        }

        int index = 0;
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (int val : bucket) {
                arr[index++] = val;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {42, 13, 75, 29, 88, 5, 61, 37};

        System.out.print("Before: ");
        for (int v : data) System.out.print(v + " ");

        bucketSort(data);

        System.out.print("\nAfter:  ");
        for (int v : data) System.out.print(v + " ");
    }
}

Output:

Before: 42 13 75 29 88 5 61 37
After:  5 13 29 37 42 61 75 88

Floating-Point Variant

Bucket sort is classically defined for floating-point values in [0, 1):

public static void bucketSortFloat(double[] arr) {
    int n = arr.length;
    List<List<Double>> buckets = new ArrayList<>(n);
    for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());

    for (double val : arr) {
        int index = (int)(val * n);
        if (index == n) index = n - 1;
        buckets.get(index).add(val);
    }

    int pos = 0;
    for (List<Double> bucket : buckets) {
        Collections.sort(bucket);
        for (double val : bucket) arr[pos++] = val;
    }
}

// Usage:
double[] data = {0.72, 0.17, 0.39, 0.55, 0.14, 0.81};
bucketSortFloat(data);
// Result: 0.14 0.17 0.39 0.55 0.72 0.81

Time and Space Complexity

The worst case happens when input is highly skewed — all elements cluster in one bucket and the inner sort dominates.

When to Use Bucket Sort

Good fit:

• Input values are uniformly distributed across a known finite range
• Sorting floating-point numbers between 0 and 1
• You need average O(n) performance and can afford O(n + k) extra memory

Poor fit:

• Input is skewed (bucket sort degrades to O(n²))
• The value range is unknown or extremely large
• Memory is constrained
• You need a guaranteed worst-case bound — use merge sort instead

Bucket Sort vs. Other Algorithms

For production use, Java's Arrays.sort() uses dual-pivot quicksort for primitives and Timsort for objects — both highly optimized. Implement bucket sort when you have a measured bottleneck and know your data distribution is uniform.

Sorting a 1D array is a one‑liner with Arrays.sort(arr). But what about a 2D array where you need to sort rows by the first column, then use the second column as a tiebreaker? Java's Arrays.sort() accepts a Comparator for this exact scenario, and there are three styles to write one — a named class, an anonymous class, and a lambda. Let's walk through all of them.

Why This Matters – A Personal Story

Early in my career, I was building a schedule optimiser for a logistics company. We had a 2D array of shipment records: [priority, weight, destinationId]. We needed to sort by priority, then weight, then destination – and I spent hours writing custom sorting loops, only to introduce subtle bugs.

Then a senior developer showed me Arrays.sort() with a comparator. It was a revelation. What I'd been writing in 50 lines of error‑prune code became a clean, one‑line lambda. That's when I realised that the Java collections framework has already solved most of your problems – you just need to know how to use it.

The Problem

Given a 2D array of integers where each row has two values, sort rows by the first column in ascending order. When two rows have the same first value, sort by the second column in ascending order:

int[][] arr = {
    {20, 25},
    {10, 15},
    {10, 25},
    {20, 15}
};

// Expected after sorting:
// {10, 15}  ← first column = 10, second = 15
// {10, 25}  ← first column = 10, second = 25
// {20, 15}  ← first column = 20, second = 15
// {20, 25}  ← first column = 20, second = 25

The Key: What Arrays.sort() Needs

Arrays.sort(T[] array, Comparator<T> comparator) sorts an array of objects using a custom comparison function. Since each row of a 2D array is an int[], you need a Comparator<int[]> that compares two rows.

The comparator returns:

• A negative number if the first argument should come before the second
• Zero if they are equal
• A positive number if the first argument should come after the second

Style 1: Named Comparator Class

Cleanest for reusable or complex comparators:

import java.util.Arrays;
import java.util.Comparator;

class MultiDimArrayComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] m, int[] n) {
        if (m[0] == n[0]) {
            return m[1] - n[1]; // tiebreak on second column
        }
        return m[0] - n[0]; // primary sort on first column
    }
}

public class SortDemo {
    public static void main(String[] args) {
        int[][] arr = {{20,25},{10,15},{10,25},{20,15}};
        Arrays.sort(arr, new MultiDimArrayComparator());

        for (int[] row : arr) {
            System.out.println(row[0] + " " + row[1]);
        }
    }
}

10 15
10 25
20 15
20 25

Style 2: Anonymous Class

When you only need the comparator in one place and don't want to create a separate class file:

Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] m, int[] n) {
        return m[0] == n[0] ? m[1] - n[1] : m[0] - n[0];
    }
});

Same logic, less boilerplate. The ternary operator keeps it compact.

Style 3: Lambda (Java 8+)

Since Comparator is a functional interface, you can express it as a lambda for maximum conciseness:

Arrays.sort(arr, (m, n) -> m[0] == n[0] ? m[1] - n[1] : m[0] - n[0]);

This is the style you'll see most often in modern Java code. All three styles produce identical results.

Sorting in Descending Order

Just reverse the comparison — swap m and n:

// Descending by first column, descending by second on tie
Arrays.sort(arr, (m, n) -> n[0] == m[0] ? n[1] - m[1] : n[0] - m[0]);

for (int[] row : arr) System.out.println(row[0] + " " + row[1]);
// 20 25
// 20 15
// 10 25
// 10 15

Using Comparator.comparingInt() — The Fluent Way

Java's Comparator class has factory methods for building multi‑level comparators cleanly:

import java.util.Comparator;

Arrays.sort(arr,
    Comparator.comparingInt((int[] row) -> row[0])
              .thenComparingInt(row -> row[1])
);

for (int[] row : arr) System.out.println(row[0] + " " + row[1]);
// 10 15
// 10 25
// 20 15
// 20 25

The .thenComparingInt() chaining makes multi‑column sorting read like English: "sort by column 0, then by column 1." This is particularly clean when you have three or more columns to sort by.

Real‑World Example: Sorting Meeting Intervals

A classic interview problem — given a list of meeting intervals [start, end], sort them by start time (and by end time on ties) to process them chronologically:

int[][] meetings = {
    {9, 11},
    {8, 10},
    {9, 10},
    {14, 15},
    {8, 9}
};

Arrays.sort(meetings, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

System.out.println("Sorted meetings:");
for (int[] m : meetings) {
    System.out.printf("[%d, %d]%n", m[0], m[1]);
}
// [8, 9]
// [8, 10]
// [9, 10]
// [9, 11]
// [14, 15]

A Word on Integer Overflow

The subtraction trick (m[0] - n[0]) is a fast way to write a comparator, but it can overflow when values are extreme (e.g., Integer.MAX_VALUE - Integer.MIN_VALUE overflows). For interview problems with constrained inputs it's fine, but for production code prefer:

// Safe — no overflow risk
Arrays.sort(arr, (m, n) -> Integer.compare(m[0], n[0]) != 0
    ? Integer.compare(m[0], n[0])
    : Integer.compare(m[1], n[1]));

// Or more concisely using Comparator chain:
Arrays.sort(arr, Comparator.comparingInt((int[] r) -> r[0]).thenComparingInt(r -> r[1]));

Comparing with Strings and Other Types

The same pattern works for arrays of strings, objects, or any type. Here's a 2D array of strings sorted by the first column lexicographically, then by the second:

String[][] people = {
    {"Alice", "Engineer"},
    {"Bob", "Manager"},
    {"Alice", "Designer"},
    {"Charlie", "Architect"}
};

Arrays.sort(people, Comparator
    .comparing((String[] row) -> row[0])
    .thenComparing(row -> row[1])
);

for (String[] p : people) {
    System.out.println(p[0] + " - " + p[1]);
}
// Alice - Designer
// Alice - Engineer
// Bob - Manager
// Charlie - Architect

The fluent Comparator.comparing() works with any type that implements Comparable (like String), and you can use .thenComparing() for subsequent columns.

How I Teach This to Juniors

When I mentor junior developers, I break this down into three steps:

1. Understand that each row is an object. In a 2D array int[][] arr, each row is an int[]. So you're sorting an array of objects – that's why you need a Comparator.
2. Write the comparison logic in plain English. For example: "If two rows have different first elements, put the smaller first element first. If they have the same first element, put the smaller second element first." Then translate that to code.
3. Choose the right style. For a one‑off sort, use a lambda or fluent comparator. For a reusable rule, use a named class.

Once they get this, they're no longer afraid of custom sorting – and it opens up a whole new world of data manipulation.

Summary

To sort a 2D array in Java, pass a Comparator<int[]> to Arrays.sort(). The comparator receives two rows and returns negative, zero, or positive to indicate their relative order. For multi‑column sorting (primary column first, secondary as tiebreaker), use a ternary expression or chain Comparator.comparingInt().thenComparingInt().

Key takeaways:

• Use a lambda for inline sorting – it's concise and readable.
• Use Comparator.comparingInt() for multi‑column sorting – it's fluent and safe.
• Avoid the subtraction trick for large integers – use Integer.compare() to prevent overflow.
• For reusable logic, extract the comparator to a named class or a static field.
• Practice with real examples – meeting intervals, priority queues, and CSV processing.

This is one of those skills that pays off every time you work with tabular data. I've used it in analytics, logistics, and financial systems – and I keep coming back to it. Master this, and you'll never waste time writing manual sorting loops again.

Happy coding – and may your data always be sorted as you expect!