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.

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.

Canonical examples

Merge sort implementation

The two-pointer merge step is what makes merge sort worth studying independently of the sort itself. The same linear scan appears in "merge k sorted lists" (with a heap replacing the two pointers), "merge sorted array" (in-place from the back), and interval merging problems. Recognizing the merge pattern is the key transfer skill.

Merge intervals

Sort by start time, then scan: if the current interval overlaps the last merged interval (current start ≤ last end), extend the last interval's end. Otherwise, start a new interval. Sorting first reduces an O(n^2) pairwise overlap check to a single O(n) scan - after sorting, overlapping intervals are always adjacent.

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).

Practice problems

• Merge Intervals - Sort by start, scan and merge overlapping intervals.
• Sort Colors - Dutch national flag; three-way partition in O(n) time O(1) space.
• Largest Number - Custom comparator: compare a+b vs b+a as strings.
• Meeting Rooms - Sort by start, check consecutive pairs for overlap.
• Sort List - Merge sort on a linked list; the natural fit for pointer-based structures.
• Find K Pairs with Smallest Sums - Heap plus sorted structure; combines sorting and heap patterns.