Sorting and searching

You will almost never write a sort. You will choose one, rely on its guarantees, and occasionally be surprised by which guarantee you did not have — so this lesson is about what Java actually runs and what it promises.

#Two different sorts, chosen by the type

Arrays.sort(int[] xs)        // dual-pivot quicksort
Arrays.sort(Object[] xs)     // TimSort
Collections.sort(list)       // TimSort, via Arrays.sort

That split is deliberate and worth knowing the reason for.

Primitives get dual-pivot quicksort. In place, no extra array, excellent cache behaviour — and not stable, which does not matter, because two ints with the same value are indistinguishable. There is nothing to preserve.

Objects get TimSort. It allocates temporary space and it is stable, which for objects matters enormously — and the next section is why.

#Stability is a guarantee you will want before you know you want it

A stable sort keeps equal elements in the order they were already in.

Five employees, sorted by department only:

###   ana/eng cy/eng ed/eng bo/ops di/ops

ana, cy and ed kept the order they had in the input. That is stability, and it is what makes sorting by two things work without a compound comparator:

list.sort(comparing(Emp::name));      // sort by name first
list.sort(comparing(Emp::dept));      // then by dept — names stay ordered within each dept

With an unstable sort that second line would scramble the first. You would have to write comparing(Emp::dept).thenComparing(Emp::name) — which is clearer anyway and the better habit, but the point is that Java's object sort gives you the choice, and its primitive sort does not.

TimSort earns its keep in a second way: it detects runs that are already ordered and merges them, so nearly-sorted data is close to O(n) rather than O(n log n). Real data is very often nearly sorted — appended in time order, re-sorted after a small edit — and that is why TimSort is the default in Java, Python and elsewhere.

#Binary search, and the precondition nobody enforces

###   array    : [5, 2, 9, 1, 7]
###   search 9 : 2   <- correct, by luck
###   search 1 : -1  <- not found, but 1 is at index 3

Arrays.binarySearch on an unsorted array does not throw, does not warn, and is sometimes right. Searching for 9 returned the correct index. Searching for 1 said "not present" about an element sitting at index 3.

That is the worst failure mode available: an operation that works often enough to pass a test and fails on data you did not try. The precondition is in the Javadoc and nowhere in the type system, which means it is your job:

The array must be sorted prior to making this call. If it is not sorted, the results are undefined.

And "undefined" here does not mean an exception. It means whatever the halving happens to land on.

Binary search is O(log n) and the arithmetic is worth internalising: a billion elements is thirty steps. Which is the same shape as a database index — the indexes lesson's B-tree is binary search generalised to disk, and it is why a where id = ? on a huge table is instant.

#Which searching, actually

That last row is the decision that matters in ordinary code, and it is nearly always the right one. Sorting costs O(n log n) once; a hash set costs O(n) to build and O(1) per query. If you are searching more than a handful of times, the set wins outright and needs no precondition anybody can break.

#The comparator contract, which sorting enforces at run time

A comparator must be consistent: if a < b and b < c then a < c, and compare(a,b) must be the negation of compare(b,a).

Break it and TimSort will, sometimes, throw:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

It is thrown from the merge, so it appears on some inputs and not others, and typically in production on a larger data set than your tests had. The classic cause is a comparator that subtracts — a.value - b.value — which overflows for large or negative values and produces the wrong sign. Use Integer.compare(a, b).

The comparable-and-comparator lesson in the collections course takes the contract apart properly, including consistency with equals.