Time Complexity of Sorting Algorithms

Problem Discuss the time complexities of the common sorting algorithms and when you would choose each.

Be ready to discuss

• Bubble, insertion, and selection sort: O(n^2) average and worst case; insertion sort hits O(n) on nearly-sorted input and is genuinely the fastest choice for tiny arrays.
• Merge sort: O(n log n) in every case, stable, but needs O(n) auxiliary space - the reason it wins for linked lists (where merging needs no extra space) and external sorting.
• Quick sort: O(n log n) average, O(n^2) worst case on adversarial or already-sorted input with a naive pivot; O(log n) recursion stack; in-place and cache-friendly, which is why it usually beats merge sort in practice.
• Pivot strategies that avoid the worst case: randomised pivot, median-of-three, and introsort's fallback to heap sort at depth limit.
• Heap sort: guaranteed O(n log n) with O(1) extra space, but not stable and poor cache locality, so it's slower than quicksort in the average case.
• Stability: what it means and when it actually matters - multi-key sorting where a previous ordering must be preserved.
• The O(n log n) comparison lower bound, and how counting/radix/bucket sort beat it by not comparing - at the cost of assumptions about the key domain.
• What real libraries ship: Timsort (Python, Java objects) and introsort/pdqsort (C++, Rust) - hybrids that switch strategy based on input size and structure.
• The full trade-off axes to name: time, space, stability, adaptivity, and cache behaviour.