Compare Common Sorting Complexities

Context

Sorting is a core topic in coding interviews because it tests algorithm analysis, trade-offs, and understanding of recursion and data movement.

Question

At Stripe, you are asked to discuss the time complexity of commonly used sorting algorithms. Explain the best-case, average-case, and worst-case time complexity of major algorithms such as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, and Heap Sort.

Address these specific points:

1. Why do some algorithms have different best, average, and worst cases?
2. Which algorithms are stable, and why does stability matter?
3. When would you prefer one sorting algorithm over another in practice?

Scope Guidance

You do not need to implement the algorithms in full, but you should be able to compare them clearly, explain the source of their complexity, and mention practical trade-offs such as memory usage, recursion behavior, and performance on nearly sorted input.