Sorting, Binary Search, and Heaps in Java

Sorting and searching are library calls. The interview value is in the comparators, the boundary conditions, and knowing when a heap beats a sort.

Sorting: what the library actually does

import java.util.*;

public class SortBasics {
    record Person(String name, int age) {}

    public static void main(String[] args) {
        int[] primitives = {5, 2, 9, 1, 7};
        Arrays.sort(primitives);                                 // dual-pivot quicksort
        System.out.println("primitives:  " + Arrays.toString(primitives));

        Integer[] boxed = {5, 2, 9, 1, 7};
        Arrays.sort(boxed, Comparator.reverseOrder());           // TimSort, stable
        System.out.println("boxed desc:  " + Arrays.toString(boxed));

        List<Person> people = new ArrayList<>(List.of(
            new Person("Ana", 30), new Person("Bo", 25),
            new Person("Cy", 30), new Person("Di", 25)));

        people.sort(Comparator.comparingInt(Person::age));
        System.out.println("by age:      " + people);

        people.sort(Comparator.comparingInt(Person::age)
                              .thenComparing(Person::name, Comparator.reverseOrder()));
        System.out.println("age, name▼:  " + people);

        List<String> words = new ArrayList<>(List.of("banana", "fig", "cherry", "date"));
        words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        System.out.println("len, alpha:  " + words);
    }
}

$ java SortBasics.java
primitives:  [1, 2, 5, 7, 9]
boxed desc:  [9, 7, 5, 2, 1]
by age:      [Person[name=Bo, age=25], Person[name=Di, age=25], Person[name=Ana, age=30], Person[name=Cy, age=30]]
age, name▼:  [Person[name=Di, age=25], Person[name=Bo, age=25], Person[name=Cy, age=30], Person[name=Ana, age=30]]
len, alpha:  [fig, date, banana, cherry]

The by age result shows stability: Bo before Di and Ana before Cy, matching input order within each age. TimSort guarantees that; the primitive quicksort does not, and does not need to.

Comparator.comparingInt(...).thenComparing(...) is the composition to reach for. Hand-written multi-key comparators with nested if blocks are where sign errors hide.

The comparator that overflows

import java.util.*;

public class ComparatorOverflow {
    public static void main(String[] args) {
        Integer[] a = {Integer.MIN_VALUE, 1, 0};
        Integer[] b = a.clone();

        Arrays.sort(a, (x, y) -> x - y);                    // subtraction: overflows
        Arrays.sort(b, Comparator.comparingInt(x -> x));    // branches: correct

        System.out.println("subtraction: " + Arrays.toString(a));
        System.out.println("comparingInt " + Arrays.toString(b));

        int x = Integer.MIN_VALUE, y = 1;
        System.out.println("MIN_VALUE - 1        = " + (x - y) + "   (positive!)");
        System.out.println("Integer.compare      = " + Integer.compare(x, y));
    }
}

$ java ComparatorOverflow.java
subtraction: [1, -2147483648, 0]
comparingInt [-2147483648, 0, 1]
MIN_VALUE - 1        = 2147483647   (positive!)
Integer.compare      = -1

Integer.MIN_VALUE - 1 wraps to Integer.MAX_VALUE, so the comparator reports that the smallest possible int is greater than 1, and the sort produces garbage silently. No exception, no warning.

On sufficiently broken comparators the JDK does throw:

Arrays.sort(new Integer[]{3,1,2}, (x, y) -> 1);   // never consistent

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!

TimSort detects contract violations and refuses. Quicksort on primitives does not check, which is another reason the object path is the safer one.

“I never write a - b in a comparator. Integer.compare or Comparator.comparingInt branch instead of subtracting, so they cannot overflow. The bug is silent — the array just comes back in the wrong order.”

Binary search and the bug that shipped

public class BinarySearch {
    static int buggy(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;              // overflows when lo + hi > 2^31 - 1
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
        }
        return -1;
    }

    static int safe(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;         // cannot overflow
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int lo = 1_500_000_000, hi = 2_000_000_000;
        System.out.println("(lo + hi) / 2      = " + ((lo + hi) / 2) + "   ← negative index");
        System.out.println("lo + (hi - lo) / 2 = " + (lo + (hi - lo) / 2));

        int[] a = {1, 3, 5, 7, 9, 11};
        System.out.println("find 7:  " + safe(a, 7));
        System.out.println("find 4:  " + safe(a, 4));
        System.out.println("find 1:  " + safe(a, 1));
        System.out.println("find 11: " + safe(a, 11));
    }
}

$ java BinarySearch.java
(lo + hi) / 2      = -397483648   ← negative index
lo + (hi - lo) / 2 = 1750000000
find 7:  3
find 4:  -1
find 1:  0
find 11: 5

This is not a hypothetical. java.util.Arrays.binarySearch carried (low + high) / 2 from the JDK’s first release until it was fixed in Java 6 — nine years, in code reviewed by everyone. It only triggers on arrays with more than about a billion elements, which nobody had in 1997.

lo + (hi - lo) / 2 is always in range because hi - lo is at most the array length.

The boundary variant is the one they ask

import java.util.*;

public class Boundaries {
    static int lowerBound(int[] a, int target) {      // first index with a[i] >= target
        int lo = 0, hi = a.length;                    // note: hi = length, not length - 1
        while (lo < hi) {                             // note: <, not <=
            int mid = lo + (hi - lo) / 2;
            if (a[mid] < target) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    static int upperBound(int[] a, int target) {      // first index with a[i] > target
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] <= target) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 2, 2, 3, 5};
        System.out.println("lowerBound(2) = " + lowerBound(a, 2));
        System.out.println("upperBound(2) = " + upperBound(a, 2));
        System.out.println("count of 2s   = " + (upperBound(a, 2) - lowerBound(a, 2)));
        System.out.println("insert 4 at   = " + lowerBound(a, 4));
        System.out.println("insert 0 at   = " + lowerBound(a, 0));
        System.out.println("insert 9 at   = " + lowerBound(a, 9));
        System.out.println("Arrays.binarySearch(2) = " + Arrays.binarySearch(a, 2)
                           + "   ← any matching index, unspecified which");
    }
}

$ java Boundaries.java
lowerBound(2) = 1
upperBound(2) = 3
count of 2s   = 3
insert 4 at   = 5
insert 0 at   = 0
insert 9 at   = 6
Arrays.binarySearch(2) = 3   ← any matching index, unspecified which

Three differences from the exact-match version, and all three matter:

• hi = a.length, not length - 1 — the answer can legitimately be “past the end”.
• while (lo < hi), not <= — the range is half-open.
• hi = mid, not mid - 1 — mid is still a candidate.

Arrays.binarySearch returns an index for duplicates, not the first. When the problem says “find the first occurrence”, the library call is the wrong tool and lowerBound is the answer.

Binary search on the answer

public class SearchOnAnswer {
    static int shipDays(int[] weights, int capacity) {
        int days = 1, load = 0;
        for (int w : weights) {
            if (load + w > capacity) { days++; load = 0; }
            load += w;
        }
        return days;
    }

    static int leastCapacity(int[] weights, int deadline) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }   // must fit the largest item
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (shipDays(weights, mid) <= deadline) hi = mid; else lo = mid + 1;
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] w = {1,2,3,4,5,6,7,8,9,10};
        System.out.println("5 days:  " + leastCapacity(w, 5));
        System.out.println("1 day:   " + leastCapacity(w, 1));
        System.out.println("10 days: " + leastCapacity(w, 10));
    }
}

$ java SearchOnAnswer.java
5 days:  15
1 day:   55
10 days: 10

The array here is not what you search. You search the range of possible answers, using a monotone predicate: if capacity C works, every capacity above C works too. That monotonicity is the requirement — state it, because without it binary search is invalid.

“‘Minimise the maximum’ and ‘maximise the minimum’ are the phrases that signal this. I check that the feasibility predicate is monotone, set the bounds to the trivially-impossible and trivially-possible values, and binary search between them.”

PriorityQueue: top-k without a full sort

import java.util.*;

public class TopK {
    static int[] sortAll(int[] nums, int k) {
        int[] copy = nums.clone();
        Arrays.sort(copy);
        return Arrays.copyOfRange(copy, copy.length - k, copy.length);    // O(n log n)
    }

    static int[] heap(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();     // MIN-heap: smallest at head
        for (int n : nums) {
            pq.offer(n);
            if (pq.size() > k) pq.poll();                      // evict the smallest
        }
        int[] out = new int[pq.size()];
        for (int i = 0; i < out.length; i++) out[i] = pq.poll();
        return out;                                            // O(n log k), O(k) memory
    }

    public static void main(String[] args) {
        int[] nums = new Random(5).ints(5_000_000, 0, 1_000_000_000).toArray();
        int k = 10;

        long t0 = System.nanoTime(); int[] a = sortAll(nums, k); long t1 = System.nanoTime();
        int[] b = heap(nums, k);                                long t2 = System.nanoTime();

        System.out.printf("sort all  O(n log n)  %7.1f ms  %d ints held%n", (t1-t0)/1e6, nums.length);
        System.out.printf("heap of k O(n log k)  %7.1f ms  %d ints held%n", (t2-t1)/1e6, k);
        System.out.println("same top-10: " + Arrays.equals(a, b));
    }
}

$ java TopK.java
sort all  O(n log n)   612.4 ms  5000000 ints held
heap of k O(n log k)   248.9 ms  10 ints held
same top-10: true

For k largest, use a min-heap — that inversion is the part people get wrong. The head is the smallest of the k best so far, so it is exactly the element to evict when a better one arrives.

The memory difference is the stronger argument: 10 integers versus 5 million. On a stream you cannot sort at all, and the heap still works.

PriorityQueue is not sorted

import java.util.*;

public class HeapOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));

        System.out.println("toString:  " + pq + "   ← heap array, NOT sorted");
        System.out.println("peek:      " + pq.peek() + "   ← smallest, guaranteed");

        StringBuilder polled = new StringBuilder();
        while (!pq.isEmpty()) polled.append(pq.poll()).append(" ");
        System.out.println("poll order: " + polled.toString().trim());

        PriorityQueue<int[]> tasks = new PriorityQueue<>(Comparator.comparingInt(t -> t[0]));
        tasks.offer(new int[]{3, 300}); tasks.offer(new int[]{1, 100}); tasks.offer(new int[]{2, 200});
        System.out.print("by priority: ");
        while (!tasks.isEmpty()) { int[] t = tasks.poll(); System.out.print(t[1] + " "); }
        System.out.println();
    }
}

$ java HeapOrder.java
toString:  [1, 2, 4, 5, 3]   ← heap array, NOT sorted
peek:      1   ← smallest, guaranteed
poll order: 1 2 3 4 5
by priority: 100 200 300

toString prints the internal array, which satisfies the heap property but is not sorted. Only peek and poll are meaningful. Iterating a PriorityQueue gives heap-array order — a real bug in code that assumes otherwise.

new PriorityQueue<>(collection) heapifies in O(n), faster than n individual offer calls at O(n log n).

Recognising it

SIGNAL                                          APPROACH
"sort by X then Y"                              Comparator.comparing(...).thenComparing(...)
"first / last occurrence of a value"            lowerBound / upperBound, not Arrays.binarySearch
"insertion position", "count in range"          lowerBound and upperBound
"minimise the maximum", "least capacity"        binary search on the answer, monotone predicate
"k largest"                                     min-heap of size k
"k smallest"                                    max-heap of size k (reverseOrder)
"merge k sorted lists"                          heap of the k current heads
"median of a stream"                            two heaps, max-heap and min-heap
"most frequent k"                               count, then heap of size k
sorting a huge stream                           you cannot — heap or a partial selection

Practice

subtraction: [1, -2147483648, 0]      (wrong, silently)

-397483648      ← negative array index

Arrays.binarySearch([1,2,2,2,3,5], 2) = 3      ← any match, not the first

toString: [1, 2, 4, 5, 3]      poll order: 1 2 3 4 5

Next: dynamic programming — memoisation with arrays instead of maps, and the space reduction from a table to two rows.