Sorting and Searching

When to use

• Selecting a sorting algorithm based on stability, memory, key type, or data distribution
• Implementing lower/upper bound binary search or binary search on an answer space
• Finding the k-th smallest element or maintaining a streaming median
• Implementing single-pattern (KMP, Boyer-Moore) or multi-pattern (Aho-Corasick) string matching
• Building suffix arrays for repeated substring queries on large texts
• Sorting datasets that exceed available memory (external k-way merge sort)

Core principles

1. Timsort wins on real-world data — natural runs and partial ordering are the norm, not the exception
2. Radix sort beats comparison sorts when key range is bounded — O(dn) < O(n log n) when d is small
3. Binary search on the answer, not just the array — if you can check feasibility in O(f(n)), you can binary search the answer space
4. Boyer-Moore is sublinear on average — for single-pattern search on natural text it reads fewer characters than the input length
5. Aho-Corasick when patterns > 1 — one pass over the text regardless of how many patterns you search for