Sorting foundations

A comparison sort learns about the data only by asking “is a before b?”. Bubble, selection, insertion, merge, quick and heap sort are all comparison sorts.

Any comparison sort needs Ω(n log n) comparisons in the worst case (proved in Chapter 18). Counting, radix and bucket sort beat that bound because they inspect key values directly instead of comparing.

• Elementary sorts in this chapter are O(n²) but simple, in-place and fast for small n.
• Production sorts switch to insertion sort for small subarrays for exactly that reason.

You often sort records by one field, the key. In Java, Comparable defines a type's natural order, and a Comparator supplies any other order.

Never subtract to compare (a - b): it can overflow for large or negative values. Use Integer.compare or Comparator.comparingInt.

1record Student(String name, int grade, int age) {}
2
3List<Student> list = new ArrayList<>(students);
4list.sort(Comparator.comparingInt(Student::grade));           // key = grade
5list.sort(Comparator.comparingInt(Student::grade)
6               .thenComparing(Student::name));               // tie-breaker
7
8// Avoid: (a, b) -> a.grade() - b.grade()   overflows for extreme values

Reversing the comparison reverses the order. Every algorithm on this page can sort descending by flipping > to <.

For primitive arrays, Arrays.sort(int[]) has no comparator, so sort ascending and then reverse, or box to Integer[] and use Comparator.reverseOrder().

1Integer[] boxed = {5, 1, 4};
2Arrays.sort(boxed, Comparator.reverseOrder());   // [5, 4, 1]
3
4list.sort(Comparator.comparingInt(Student::grade).reversed());

A sort is stable if records with equal keys stay in their original relative order. This matters when you sort by one key after another, for example by name and then by grade: a stable second sort keeps names ordered within each grade.

In the demo below, letters mark the original order of equal values. Stable sorts keep a before b; selection sort and shell sort can break it.

An in-place sort uses O(1) extra memory (or O(log n) for recursion) and rearranges the input itself. An out-of-place sort builds the result in a separate buffer.

All elementary sorts here are in-place. Merge sort is the classic out-of-place sort, with an O(n) buffer.

An adaptive sort runs faster when the input is already partly sorted. Insertion sort does work proportional to the number of inversions (pairs out of order), so nearly sorted input sorts in close to O(n).

Selection sort is not adaptive: it always scans the whole unsorted part to find the minimum.