Chapter 23 Key Takeaways: Searching and Sorting

Chapter 23 Key Takeaways: Searching and Sorting

Linear search is O(n); binary search is O(log n). Binary search requires sorted data but reduces a million-element search from a million comparisons to twenty.
O(n²) sorts (selection, insertion) are fine for small data. For arrays under about 50 elements, the simplicity and low overhead of these algorithms often beats O(n log n) methods.
Insertion sort is adaptive. It runs in O(n) on nearly-sorted data, making it ideal for maintaining order when a few elements are added to an already-sorted collection.
Merge sort guarantees O(n log n) and is stable. It never degrades to O(n²) regardless of input, and it preserves the relative order of equal elements. Its downside is O(n) extra memory.
Quicksort is typically the fastest sort in practice. Its O(n log n) average case, in-place operation, and excellent cache locality make it the default sort in most libraries. But beware: poor pivot selection can cause O(n²) worst case.
Pivot selection matters. Median-of-three or random pivot selection prevents quicksort's worst case on sorted or nearly-sorted input — exactly the kind of data you are most likely to encounter.
Use comparison functions to sort records by different fields. Passing a comparison function to a generic sort routine separates the sorting algorithm from the sorting criterion, enabling reuse.
Composed comparisons handle multi-field sorting. Compare by the primary key first; if equal, compare by the secondary key; if still equal, compare by the tertiary key. This pattern scales to any number of criteria.
Stability matters for multi-criteria sorting. A stable sort preserves previous ordering among equal elements, which is essential when sorting by one field after another.
Use library sorts in production; write your own for understanding. The built-in TFPGList.Sort and similar facilities are well-tested and optimized. Implement sorting algorithms by hand to learn their properties and to handle special cases.