Sorting is one of the most fundamental operations in computer science — and one you rarely implement from scratch in real production code, since every language ships a solid built-in sort. So why does every DSA course spend so much time on it? Because sorting algorithms are the clearest possible teaching ground for the tradeoffs that show up everywhere else: time complexity, space complexity, stability, and the difference between "works" and "works well at scale."

This post is the map for the sorting algorithms covered across this course. Each one gets its own deeper post, but here's how they stack up against each other at a glance.

Why Sorting Still Matters

Binary search, efficient joins in databases, duplicate removal, finding the median, scheduling problems — a huge number of algorithms either require sorted input or become dramatically faster once the data is sorted. Understanding how different sorting algorithms achieve their speed (or fail to) teaches you to recognize the same patterns — divide and conquer, greedy choices, clever use of extra memory — in problems that have nothing to do with sorting at all.

Comparison Table

Algorithm        Best       Average     Worst       Space    Stable   In-Place
Bubble Sort      O(n)       O(n^2)      O(n^2)      O(1)     Yes      Yes
Selection Sort   O(n^2)     O(n^2)      O(n^2)      O(1)     No       Yes
Insertion Sort   O(n)       O(n^2)      O(n^2)      O(1)     Yes      Yes
Merge Sort       O(n log n) O(n log n)  O(n log n)  O(n)     Yes      No
Quick Sort       O(n log n) O(n log n)  O(n^2)      O(log n) No       Yes
Heap Sort        O(n log n) O(n log n)  O(n log n)  O(1)     No       Yes
Counting Sort    O(n + k)   O(n + k)    O(n + k)    O(n + k) Yes      No

Three terms in that table are worth pinning down before moving on:

Stability, In-Place, and Why They Matter

A sort is stable if it preserves the relative order of equal elements. Imagine sorting a list of orders by date, where several orders share the same date — a stable sort keeps those same-date orders in their original relative order; an unstable sort might shuffle them. This matters whenever you sort by one key but care about the order of ties on a second key.

A sort is in-place if it rearranges the data using only O(1) (or very little) extra memory, rather than allocating a second array. Merge sort, for example, is not in-place in its classic form — it needs auxiliary arrays during the merge step — which is why it uses O(n) space in the table above, while quick sort and heap sort can rearrange the array directly.

Which One Should You Actually Use?

In practice, you'll almost always call a language's built-in sort (Python's sorted()/.sort(), which uses an algorithm called Timsort — a hybrid of merge sort and insertion sort tuned for real-world data). Knowing the algorithms underneath still matters for two reasons: technical interviews frequently ask you to implement or reason about them, and understanding their complexity helps you predict how your own code will scale as input size grows.

The posts on Bubble, Selection, and Insertion Sort, Merge Sort, Quick Sort, and Heap/Counting Sort each walk through the mechanics and code for the algorithms summarized in the table above.