Even something as commonplace as "putting data in order" has many algorithms behind it. Each has its own strengths and weaknesses, and the optimal choice changes with the volume and nature of the data you handle. In this article we organize seven representative methods using a single shared yardstick: time complexity.
What is time complexity (Big-O notation)?
When comparing how fast algorithms are, we evaluate them not by raw execution time but by "how the amount of work grows as the number of data items n increases." This is called Big-O notation (O notation).
O(n²)… when n grows 10x, the work grows roughly 100x. It slows down dramatically with large data sets.O(n log n)… the benchmark for practical fast sorts. Realistic even for large data.O(n)… proportional to the number of items. Theoretically among the fastest when conditions allow.
Seven representative sorts
| Algorithm | Average complexity | Worst-case complexity | Stability | Characteristics |
|---|---|---|---|---|
| Bubble sort | O(n²) | O(n²) | Stable | Repeatedly swaps adjacent items. Easy to understand but slow. |
| Selection sort | O(n²) | O(n²) | Unstable | Picks the minimum and moves it to the front. Few swaps. |
| Insertion sort | O(n²) | O(n²) | Stable | Extremely strong on nearly sorted data. |
| Shell sort | about O(n^1.3) | O(n²) | Unstable | Improves insertion sort using spaced-out gaps. |
| Merge sort | O(n log n) | O(n log n) | Stable | Divide and conquer. Reliably fast even in the worst case. |
| Quicksort | O(n log n) | O(n²) | Unstable | Among the fastest in practice. Pivot choice is key. |
| Heap sort | O(n log n) | O(n log n) | Unstable | Requires no extra memory and guarantees the worst case. |
What "stability" means
A stable sort is one that preserves the original order of elements with equal values. This matters in situations such as "if scores are tied, keep them in registration order."
The divide-and-conquer pair — merge sort and quicksort
Merge sort splits the data in half repeatedly, then merges the sorted small sequences back together to put the whole thing in order. It always guarantees O(n log n), but it requires extra memory for merging.
Quicksort partitions items into groups smaller than / larger than a reference value (the pivot) and sorts them recursively. It is extremely fast on average, but a poorly chosen pivot can lead to a worst case of O(n²). Many standard libraries adopt a hybrid approach that combines these with heap sort.
sort first (most are already optimized). Understanding the algorithms helps you estimate data volumes, analyze bottlenecks, prepare for interviews, and explain "why is this slow?"
How to choose by use case
- Few items / nearly sorted → insertion sort
- Stability required (preserving the order of equal values) → merge sort
- Raw speed, average performance first → quicksort
- Tight memory / want a guaranteed worst case → heap sort
Summary
Sorting algorithms are evaluated along several axes: time complexity, stability, and memory usage. A "fast sort" is not always the best choice; selecting one based on the nature of the data and your requirements is what matters. Start by watching their behavior with your own eyes to get a feel for each one's personality.
Frequently Asked Questions (FAQ)
What is time complexity (Big-O notation)?
It is a way of evaluating an algorithm's speed not by its raw execution time, but by how the amount of work grows as the number of data items n increases. O(n²) means that when n grows 10x, the work grows roughly 100x; O(n log n) is the benchmark for practical fast sorts; and O(n) represents work that scales in proportion to the number of items.
What is a stable sort?
A stable sort is one that preserves the original order of elements with equal values. This matters in situations such as "if scores are tied, keep them in registration order." Bubble sort, insertion sort, and merge sort are stable, while selection sort, quicksort, and heap sort are unstable.
How should I choose a sort for a given use case?
Insertion sort is good when there are few items or the data is nearly sorted; merge sort when you need stability such as preserving the order of equal values; quicksort when you want raw speed with strong average performance; and heap sort when memory is tight and you want a guaranteed worst case. In practice, the basic rule is to use your language's standard sort first.