The Question

"What are the time complexities of common sorting algorithms, and how would you compare their best, average, and worst-case behavior?"

Best, Average, and Worst Case

Sorting algorithms are usually analyzed across multiple input scenarios because their performance can vary significantly depending on input order. A strong answer should distinguish between best-case, average-case, and worst-case complexity rather than giving only one number.

Comparison-Based Sorting Lower Bound

For comparison-based sorting, the general lower bound is O(n log n) in the average and worst case for optimal algorithms. This is why algorithms like merge sort and heap sort are considered asymptotically efficient, while bubble sort and insertion sort are slower on large unsorted inputs.

Algorithm Tradeoffs

Time complexity alone is not enough to choose a sorting algorithm. Stability, memory usage, implementation complexity, and behavior on nearly sorted data also matter in practice.

Stable vs Unstable Sorting

A stable sort preserves the relative order of equal elements, which matters when sorting records by multiple keys. Merge sort and insertion sort are stable in their standard forms, while heap sort and typical quicksort implementations are not.

# Stable multi-key sorting example
items = [(2, 'a'), (1, 'x'), (2, 'b')]
# A stable sort by first field keeps ('a') before ('b')

Input Sensitivity

Some algorithms perform especially well on partially sorted input. For example, insertion sort can run in O(n) time when the array is already or nearly sorted, which makes it useful for small or almost ordered datasets.