Sorting

A broad sorting prompt should start with constraints. Comparison sorting has an Omega(n log n) lower bound in the general case. Merge sort guarantees O(n log n) time and is stable but needs O(n) extra memory. Quicksort is often fast in practice and can be in-place, but naïve pivots have O(n^2) worst case; randomized or median-like pivots reduce that risk. Heap sort gives O(n log n) worst-case time and O(1) auxiliary space but is not stable. When keys are bounded integers, counting or radix sort can beat comparison sorting at the cost of range-dependent memory. In production, prefer the language library unless the interview asks for implementation. Whatever approach you choose, state whether equal items preserve order, how null or custom comparators are handled, and why the algorithm fits the input. A sortedness pass is O(n) if verification is needed.