Sorting

What is sorting?

Sorting arranges a sequence in a defined order. Most interview sorting problems do not ask you to implement a sort - they require you to sort first, then apply a simpler algorithm to the sorted result (two pointers, greedy scan, binary search). Sorting is the preprocessing step that transforms an O(n^2) brute-force scan into an O(n log n) + O(n) solution.

Python's sorted() and list.sort() use Timsort, a hybrid merge sort and insertion sort that is O(n log n) worst case and stable. For custom ordering, pass a key= function that maps each element to a comparison key. For reverse order, pass reverse=True. Avoid implementing comparator functions directly - use functools.cmp_to_key() only when a key= function cannot express the comparison (rare; the main case is string concatenation ordering like in "Largest Number").

Two algorithms are worth knowing from first principles: merge sort (divide-and-conquer, stable, O(n log n) guaranteed, O(n) extra space) and quicksort (partition, in-place, average O(n log n), O(n^2) worst case without randomization). Merge sort is the foundation of Timsort and the natural fit for sorting linked lists - its divide and merge steps work without random access. Quicksort's partition step is the basis for the "quickselect" algorithm used to find the kth largest element in O(n) average.

The comparison lower bound: any sort that uses comparisons requires at least O(n log n) comparisons in the worst case. Counting sort and radix sort beat this by not using comparisons at all - they work by counting occurrences of bounded integer values. They apply only when the value range k is small enough that O(n + k) is better than O(n log n).

Core operations

Key patterns

Merge sort (divide and conquer)

Split the array in half, sort each half the same way, then merge the two sorted halves into one.

When to use - you need a sort with a guaranteed O(n log n) worst case and a stable order, or you are sorting a linked list where quicksort's random access does not apply. The cost is O(n) extra space for the merge buffer, which an in-place sort avoids.

How it works - the recursion bottoms out at length 0 or 1, where a list is already sorted. The merge step does the real work: scan both sorted halves with two index pointers, append the smaller front element each time, then append whatever tail remains. Every element is touched once per level and there are log n levels, which is why the recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n). Stability holds because the merge prefers the left half on a tie, so equal elements keep their original order.

Example: sort by splitting. [5, 2, 8, 1, 9, 3] splits at the midpoint into [5, 2, 8] and [1, 9, 3], and the recursion bottoms out in single cells before any merging starts. Each merge compares fronts, so the halves rebuild as [2, 5, 8] and [1, 3, 9], and the final merge walks 1, 2, 3, 5, 8 before appending the lone tail 9 in bulk: [1, 2, 3, 5, 8, 9]. The visualizer below shows each divide and merge.

Custom sort key

Sort by a derived value instead of the element itself by handing sorted() a key= function that maps each element to its comparison key.

When to use - the order you want is not the natural order of the elements: sort by a field, by a computed property, or by several criteria at once. The key= function runs once per element, so it adds only O(n) on top of the sort and keeps the call cheap.

How it works - sorted(iterable, key=func) calls func on each element, then sorts by those returned keys. For multi-criteria sorts, return a tuple - Python compares tuples lexicographically, so ties on the first field break on the second. Mix ascending and descending by negating the numeric fields you want reversed. When the order is a genuine pairwise relation that no single key can capture - the "Largest Number" case below, where you decide between two numbers by which concatenation a+b versus b+a is larger - drop to a comparator with functools.cmp_to_key, which turns a two-argument compare function into a key.

Example: build the largest combined number. For [3, 30, 34, 5, 9], the pairwise compare asks for each pair which concatenation is bigger: "330" beats "303", so 3 goes before 30, while "9..." always starts with the digit 9 and 9 sorts first overall. The order settles as 9, 5, 34, 3, 30, and concatenating gives 9534330. The visualizer below runs that compare on every pair.

When to reach for sorting

• You need to find pairs, triplets, or groups satisfying a sum or difference condition - sort first, then use two pointers.
• The problem involves intervals (meetings, ranges) that need overlap detection or merging.
• You want to apply a greedy sweep (always pick the best remaining item) - sorting enables a single left-to-right pass.
• The problem asks you to group elements by a property (frequency, remainder, leading digit) - sort by that property.
• Binary search becomes applicable once data is sorted - sort then binary search beats O(n) linear scan when you need multiple lookups.
• "Find the kth largest/smallest" - sorting is O(n log n); a heap is O(n log k) which beats sorting when k is small relative to n.
• The input is nearly sorted - Timsort degrades gracefully on nearly-sorted input, often running closer to O(n).