Sorting

Sorting Algorithms

You will rarely be asked to implement a sort, and you will often be asked which one and why. The useful knowledge here is comparative: which sorts are stable, which have a bad worst case and what triggers it, and when the O(n log n) comparison bound can be escaped entirely by not comparing at all. Custom comparators come up more often than any algorithm on the list.

3 patterns8 techniquesJava code

Where to start, and what comes next

01
Comparison Sorts
Quicksort, merge sort and heapsort. Learn them together, because the comparison between them is what gets asked.
Quick Sort Merge Sort Heap Sort
02
Linear-Time Sorts
Counting, radix and bucket sort. These beat n log n by indexing rather than comparing, subject to conditions worth knowing.
Counting Sort Radix Sort Bucket Sort
03
Sorting Tricks
Custom comparators and quickselect. The most practically useful pattern in the topic.
Custom Comparator Kth Element (QuickSelect)

If you only have time for three things

Which sorts are stable and why it matters, since stability is what lets you sort by one key and then another without losing the first.
Quicksort's O(n squared) case and that already-sorted input triggers it with a last-element pivot.
Quickselect for the kth element at O(n) average, which is faster than sorting when you only need one position.

In an interview

Know what your language actually does. Java uses dual-pivot quicksort for primitives and TimSort for objects, and the reason is stability, which cannot be observed on primitives. That answer covers several questions at once. For custom comparators, be ready to say that the contract must be transitive and consistent, because Java throws if it detects otherwise.

The idea underneath

Sorting enables 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.

Problems that use these patterns

Sort ColorsKth Largest ElementMerge IntervalsLargest NumberSort ListMeeting Rooms

Head to head

Quicksort vs Merge Sortpartition around a pivot, sort each side against split in half, sort each, merge Heap vs Binary Search Treethe extreme value, always at the root against everything in sorted position

Questions people ask

Why does Java use two different sorts?

Two equal ints are indistinguishable, so stability is unobservable and primitives get quicksort for its speed and in-place operation. Objects can compare equal and differ in every other field, so they get a stable merge sort variant.

When can I beat O(n log n)?

When you stop comparing. Counting sort indexes an array by value and is O(n + k) for a value range k. Radix sort applies it digit by digit. Both need bounded, small keys, and counting sort with a huge range is far slower than comparison sorting.

What makes a comparator wrong?

Violating transitivity or consistency. Subtracting integers is the common trap, since a - b overflows for large values and produces the wrong sign. Use Integer.compare instead.