Sorting and Searching

Sorting complexities

Built-in sorts run in $O(n \log n)$; assume that cost when a solution begins with a sort.

When to use which

• Insertion sort: tiny or nearly sorted inputs; simple, in place, and stable.
• Merge sort: guaranteed $O(n \log n)$, stable, and well suited to linked lists and to merging sorted sequences (including k sorted lists). Costs $O(n)$ extra space for arrays.
• Quick sort: fastest in practice, in place. Partitioning is also the core of quickselect, which finds the k-th largest element in $O(n)$ average time. Pick a random or median-of-three pivot to avoid the $O(n^2)$ worst case on sorted input.
• Bucket / counting sort: values come from a small known range or are uniformly distributed (for example sorting colors 0, 1, 2). Trades extra space for linear time.

Binary search

Binary search divides the search space in half at each step: check the middle element, and if it is not the target, discard the half that cannot contain it. It runs in $O(\log n)$ time and $O(1)$ space when done iteratively.

Recognition signals

• The input is sorted (or rotated sorted) and you need a value, position, or boundary
• Any monotonic property: if check(x) is true then it is true for everything larger (or smaller). Search on the answer, such as “minimum capacity / speed / days such that …”
• A required runtime of $O(\log n)$

Modified binary search applies to sorted or rotated arrays where you need a specific element: decide which half is sorted, test whether the target lies in it, and discard the other half.

Gotchas

• Use left <= right for an exact-match search and shrink with mid + 1 / mid - 1; for boundary searches use left < right and keep mid as a candidate to avoid infinite loops
• Compute mid = left + (right - left) / 2 to avoid overflow in fixed-width integer languages
• A 2D matrix with sorted rows can be treated as a flattened array, with row = mid / cols, col = mid % cols
• Duplicates can break the “which half is sorted” logic in rotated arrays

Templates

• Binary Search: search a sorted array
• Insertion Sort: in-place, stable, $O(n^2)$
• Merge Sort: divide and conquer, $O(n \log n)$
• Quick Sort: partition around a pivot
• Bucket Sort: linear-time sort over a small value range

Problems