Array & Sorting

Sorting is valuable when it makes the relationship local: duplicates become adjacent, interval endpoints can be merged in order, and two-sum can use inward pointers. Before sorting, ask whether the original order must remain intact and whether original indices must be returned. If so, sort pairs of value and original index or create a copy. Use a comparator that cannot overflow, for example compare values rather than subtracting them in languages with fixed-width integers. After sorting, state the invariant of the scan: for interval merging, the current result tail covers all processed overlapping intervals; for two pointers, moving the left pointer increases the sum and moving the right pointer decreases it. Test equal keys, negative values, already-sorted input, and unstable-order requirements. Comparison sorting is O(n log n) time; the subsequent scan is O(n), and space is O(n) if a copy or indexed pairs are needed.