Sorting algorithms
Sorting looks like one small task: put the values in order. It is also the best place to learn how algorithms are designed. This chapter moves from comparing pairs of values, to splitting the array in two, to counting values instead of comparing them at all. Every speedup comes from a different idea, not from more clever code. By the end you will be able to write these sorts, explain why each one is fast, and recognize when sorting first makes another problem easy.
Why sorting deserves its own chapter
Sorting is rarely the goal. It is the ground that many other algorithms stand on.
An interviewer will rarely ask you to write a sorting algorithm as the final answer, because every language already ships a sort. So why study them? Because sorting is a way of preparing data. Many problems look difficult while the input is in random order. Once the data is sorted, most of the difficulty is gone.
- Binary search needs a sorted array (chapter 3). Sorting is what makes it sorted.
- Merging intervals (LC 56) is hard while the intervals are in random order. After you sort them by left endpoint, two intervals that overlap are always next to each other.
- For the kth largest element (LC 215), one partition step discards a whole side of the array — about half of it on average. You never sort all of it.
- Removing duplicates, finding the most frequent value, checking whether items can be joined, and almost every greedy algorithm start the same way: sort first.
Sorting algorithms are also the best teaching material for algorithm design. In this chapter you will see divide and conquer (merge sort), randomization (quicksort), spending memory to save time (counting sort), and stability, which matters a great deal in real systems but is often covered in one line in a textbook. All of these ideas return in later chapters.
People have sorted things for centuries. Computers have done it for seventy years.
Books arranged by call number, cards arranged in your hand, one click on a spreadsheet column header: putting things in order is an old human habit. In 1945 John von Neumann wrote merge sort as one of the earliest programs for a stored-program computer. In 1959 Tony Hoare invented quicksort while working on machine translation from Russian to English, where words had to be sorted before they could be looked up in a dictionary. The history of sorting is close to the history of computer algorithms itself.
Start from the most direct ideas. You are given the unsorted list [5, 2, 9, 1, 6]. How would you put it in order? The three most natural methods are bubble sort, selection sort, and insertion sort, and all three cost O(n²) in the worst case. Do not memorize the code yet. Play each one step by step and watch where the work goes in each of them:
Three O(n²) sorts, three different invariants
Bubble, selection, and insertion sort. All three are slow on large inputs, but each one keeps a different promise after every round.
All three use two nested loops and all three cost O(n²) in the worst case. What separates them is the loop invariant: the property that is guaranteed to hold after every round. Learn the invariant and you understand the algorithm. Learn only the code and you have memorized it.
Invariant: after round i, the rightmost i values are the i largest, and they are in their final positions. Each round compares neighbors and swaps them when they are out of order. Add a flag: if a round performs zero swaps, the array is already sorted and the algorithm stops. Best O(n) (sorted input), average and worst O(n²), O(1) auxiliary space, stable.
Invariant: after round i, the leftmost i values are the i smallest, and they are in their final positions. Each round scans the whole unsorted part to find the minimum, then swaps it to the front. It performs the fewest swaps (at most n−1), but it always makes about n²/2 comparisons, so best, average, and worst are all O(n²) — sorted input does not help it at all. It is not stable: the long swap can jump an element over an equal one.
Invariant: after round i, the first i values are sorted relative to each other — but not necessarily in their final positions. It works like sorting playing cards: take the next card and slide it into the right place among the cards already in your hand. Best O(n) (sorted input), average and worst O(n²), O(1) auxiliary space, stable. It is the fastest of the three on nearly sorted data, and you will meet it again in section 06.
The three "first i values" do not mean the same thing
For bubble and selection sort, "done" means final position: those values will never move again. For insertion sort it only means sorted among themselves; a smaller card drawn later will still be inserted between them, pushing them right. That difference explains why insertion sort can stop its inner loop early, while selection sort must scan the whole unsorted part every round.
Of the three, insertion sort is the one worth writing until you can do it from memory. It is a building block of TimSort, and it is the fastest choice on data that is already nearly sorted. Here is the template in three languages. Watch the direction of the inner loop: it walks left, shifting larger values right.
key saved the original value first. Without that copy, a[j+1] = a[j] would overwrite the value you are trying to insert.Why these three are not used on large inputs
At n = 10⁵, O(n²) is about 10 billion operations, which will time out. O(n log n) is about 1.7 million. That is why submitting bubble sort for LC 912 (sort an array, n up to 5×10⁴) fails on time. These three are still worth knowing for two reasons: they teach the invariants, and on small arrays of a few dozen elements their low constant factor makes them genuinely faster. The next two sections cover the algorithms that handle large inputs.
Merge sort: the first divide and conquer algorithm here
MEDIUMWorked example A · LC 912 with merge sort — split in two, trust the recursion, then merge.
Problem (LC 912): given an unsorted array, return it sorted, in O(n log n). Brute force: any of the three sorts above — O(n²), too slow. Why it can be improved: each comparison in those sorts moves a value by one position, so very little is learned per comparison. Divide and conquer changes the plan: cut the array in half, sort each half, then combine the two sorted halves. Combining two already sorted halves takes one linear pass. That is where the time is saved.
This is also the first full use of divide and conquer in this course: divide (cut in half), conquer (sort each half recursively, assuming the recursive call does its job), and combine (merge). That assumption was introduced in the introduction, section 03, and chapter 2 covers the framework in full. The core of merge sort is the merge step, so play through it on its own first:
Once merging is clear, the whole algorithm is: split until each piece holds one element (a single element is already sorted), then merge the pieces back level by level. Here it is in three languages. Watch the line marked take the left value when they are equal — that single choice is what makes merge sort stable.
(lo + hi) // 2 is safe here. The default recursion limit is 1000; at n = 5×10⁴ the depth is about log₂(50000) ≈ 16, well inside it. The slice nums[i:mid+1] copies, so a version using plain indices allocates less — but this one is easier to read.Why merge sort is always O(n log n)
Draw the recursion as a tree. Each level halves the ranges, so there are log₂n levels. Across one level, all the merge calls together touch each of the n elements exactly once, which is O(n). Levels × cost per level = O(n log n), and this does not depend on the input order, so best, average, and worst are all the same. Chapter 2 makes this counting method formal. The cost is O(n) auxiliary space for the buffer.
| Merge sort | Best | Average | Worst | Aux space | Stable? |
|---|---|---|---|---|---|
| Time / space / stability | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Yes |
In production: sorting data that does not fit in memory
Merge sort is the basis of external sorting. To sort 1 TB of log lines with 8 GB of memory, split the data into chunks that do fit, sort each chunk and write it back to disk, then merge the sorted files together. Merging only needs to read each file forward and keep one position per file in memory. A database running ORDER BY over a large result set, and the shuffle stage of MapReduce, both work this way. Quicksort cannot be used here because it jumps to arbitrary positions, and disk is slow at that. Merge sort only reads sequentially.
Quicksort: partition is the whole idea
MEDIUMWorked example A · LC 912 with quicksort — pick a pivot, split into two groups in one pass, then sort each group.
Merge sort splits without looking at the values and does the real work while combining. Quicksort is the mirror image: it does the real work while splitting, and combining costs nothing. The operation that does the work is called partition. Choose one element as the pivot, then make one pass that moves every smaller value to the left and leaves every larger value on the right, with the pivot itself ending up on the boundary between them. After that pass, the pivot is at the index it will have in the fully sorted array, and it never moves again.
That one sentence is all of quicksort, and all of quickselect in section 07 as well. Play through one partition using the Lomuto scheme. Watch the two pointers: i marks the right edge of the "smaller than pivot" region, and j scans from left to right. Then watch how the pivot reaches its place in the final step:
With partition in place, quicksort is three lines: partition, sort the left part, sort the right part (the pivot slot is already correct, so it is skipped). One problem must be handled: how the pivot is chosen. If you always take the last element, then on an already sorted array every partition removes just one element, the recursion goes n levels deep, and the cost becomes O(n²) with a real risk of stack overflow. The fix is a random pivot: before partitioning, pick a random index and swap that element into the last position. The worst case still exists, but no particular input triggers it, so it becomes very unlikely.
| Quicksort | Best | Average | Worst | Aux space | Stable? |
|---|---|---|---|---|---|
| Time / space / stability | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ No |
The worst case happens when every partition splits the range into one element and everything else — for example, sorted input with a fixed first or last pivot. The space figure is the expected recursion stack, O(log n); in the worst case the stack is O(n). Quicksort is called in-place, which in this course means it uses O(1) or O(log n) auxiliary space — not literally zero extra memory.
How to answer: merge sort or quicksort?
"Both are O(n log n) on average. Quicksort has a smaller constant factor and is in-place (only an O(log n) expected stack), so it is the usual choice for sorting in memory — but it is not stable, its worst case is O(n²), and it needs a random pivot to make that worst case unlikely. Merge sort is stable and is O(n log n) even in the worst case, which makes it the choice when stability is required, when sorting a linked list, or when sorting data larger than memory; the cost is O(n) auxiliary space." Being able to state this trade-off is worth more than being able to write only one of them.
Hoare on what the hard part actually is
Tony Hoare invented quicksort at 26. His point about algorithms was that writing one down is not the difficult part — showing that it is correct, and why it is fast, is. The loop invariant of partition is a good example: at any point during the scan, everything at or left of i is smaller than the pivot, and everything between i and j is not. Once you can state that, the correctness of the whole algorithm follows.
Below the comparison bound: count instead of compare
Counting, bucket, and radix sort — why the Ω(n log n) bound does not apply to them.
Every sort so far decides what to do by comparing two values. For that whole family there is a proven limit: any comparison-based sort needs at least Ω(n log n) comparisons in the worst case. Note the scope carefully — the bound applies to comparison-based sorting only. It is a proof, not a statement that nobody has found something better yet. Here is the argument:
For n distinct elements there are n! possible arrangements. To be correct on every input, the algorithm must be able to tell all of them apart.
Asking "is a larger than b?" has two possible answers, so a run of the algorithm is a path down a binary decision tree. A binary tree of height h has at most 2ʰ leaves, and each leaf is one possible output order.
From 2ʰ ≥ n! we get h ≥ log₂(n!) ≈ n log₂ n. The height of the tree is the number of comparisons in the worst case, so every comparison sort needs Ω(n log n).
So how can counting sort be O(n)? Because it never compares two elements. It uses a different source of information: if you know the keys are integers within a small known range — say 0 to 100 — you can prepare one bucket per value and count, instead of asking which of two values is larger. An algorithm that makes no comparisons is not covered by the comparison bound. The condition matters more than the formula: this only works when the keys can be mapped to a bounded range of integers. Play through the two phases, counting and then writing the values back out:
The counting sort template. It uses an offset so that negative values work too: the bucket for value x is at index x - lo.
[v + lo] * c produces c copies of the same value in one step. LC 1365, "how many numbers are smaller than the current number", is counting sort plus a prefix sum and nothing else.For integers within a bounded range k. Time O(n + k), space O(k). When k is large — arbitrary 32-bit integers, for example — the bucket array does not fit in memory, and this is worse than quicksort.
Cut the value range into intervals, drop each element into its interval, then sort inside each bucket (usually with insertion sort). Close to O(n) when the values are spread evenly. If they cluster into one bucket, it falls back to the cost of the inner sort.
Sort by the ones digit, then the tens, then the hundreds — one digit per pass, using a stable counting sort each time. Time O(d(n + k)) where d is the number of digits. Useful for large integers and fixed-length strings. It only works because counting sort can be made stable: each pass must preserve the order produced by the previous one.
Non-comparison sorts are not general-purpose
They only handle data whose key can be mapped to a bounded range of integers or to buckets. You cannot use counting sort to order arbitrary objects by a custom rule — LC 179, which orders numbers by which concatenation is larger, is a good example. Anything of the form "I can compare any two items, so sort them" still needs quicksort or merge sort. Check the key range first, then decide: bounded and integral means linear time is possible; otherwise plan for O(n log n).
Stability, and what the built-in sort really is
One property that matters constantly in real systems and is often given a single line in a textbook.
A sort is stable when elements whose keys are equal keep the same relative order they had before sorting. For plain numbers this does not matter: two copies of 5 are indistinguishable, so nobody can tell which one came first. It starts to matter as soon as the elements are objects with more than one field, because then two elements can have equal keys and still be different. Try it first:
Why does it matter? Take an order table. You want it sorted by amount, and orders with the same amount sorted by the time they were placed. You can do this with two ordinary sorts: sort by time first, then sort by amount. If the second sort is stable, orders with equal amounts keep the time order from the first pass, and you are done. If the second sort is not stable, that time order is destroyed and the first pass was wasted. This is what stability buys you: sorts that can be applied one after another.
| Algorithm | Best | Average | Worst | Aux space | Stable? | What to remember |
|---|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | ✅ | Swaps neighbors only, so it is stable; the early-exit flag gives the O(n) best case |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | ✅ | O(n) on nearly sorted data; the best choice for small arrays |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | ❌ | Sorted input does not help; the long swap breaks the order of equal elements |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | Stable and O(n log n) even in the worst case; the choice for linked lists and external sorting |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | Fastest on average, so it is the default in memory; needs a random pivot |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | O(n log n) guaranteed with O(1) auxiliary space (heaps: DataData · 09) |
| Counting | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅* | No comparisons; needs integer keys in a bounded range k |
* Counting sort is stable when it is written with a prefix sum and the elements are written back from right to left. The shorter version above, which rebuilds values from the counts, is not stable. Which one you get depends on how you write it.
Now the answer to the question at the start: what is the sort you call every day actually running? Not one algorithm. Each of these libraries combines several of the algorithms in the table above, and the three languages do not behave the same way:
list.sort and sorted use TimSort and are stable. TimSort was written by Tim Peters for Python in 2002 and was later adopted by Java (for objects), Android, and V8. Prefer key= over cmp_to_key: key= computes one key per element, which is n calls, while a comparison function is called about n log n times.TimSort: insertion sort for small pieces, merge sort to join them
TimSort starts from an observation about real data: it is often already sorted in places — mostly ordered, with a few values out of position. So it first scans for stretches that are already sorted, called runs. A run that is too short is extended to a minimum length with insertion sort, which is the fastest option on short and nearly sorted pieces. Then it uses merge sort to combine the runs, which keeps the result stable. Best case O(n), worst case O(n log n), stable. It combines most of the algorithms in this chapter, and it is a good illustration that the practical question is not which algorithm is best, but which combination fits the data.
Worked example B · kth largest: you do not need a full sort
MEDIUMLC 215 — quickselect at O(n) average, compared with a heap of size K.
Problem: return the kth largest element of an array. In ascending order, the kth largest sits at index n−k. Brute force: sort everything in O(n log n) and read index n−k. That is accepted, but it does more work than the question asks for: you wanted the value at one index and you ordered all n of them. Why it can be improved: recall that partition places its pivot at its final index. After one partition, that index is known. If it is exactly n−k, return that value. If not, the answer can only be on one side, so the whole other side is discarded. This is called quickselect.
The frame-by-frame partition in section 04 is the same operation used here. The new part is that only one side is searched after each partition. If the pivot splits the range near the middle, the expected work is n + n/2 + n/4 + … = 2n = O(n):
heapq.nlargest(k, nums)[-1] or sorted(nums)[-k]. An interviewer asks for the hand- written version because the point being tested is the idea: the pivot reaches its final index, so only one side has to be searched.The other approach: a heap of size K, and how to choose
Keep a min-heap holding K elements. Walk the array; once the heap is full, compare each new value with the smallest value in the heap and replace it when the new value is larger. When the walk ends, the top of the heap is the kth largest. Time O(n log K), space O(K). This approach does not modify the input, and it works when the values arrive one at a time and cannot all be held in memory (heaps are covered in DataData · 09). The trade-off: if the data fits in memory, may be reordered, and you want the best average speed, use quickselect; if the data is a stream, is read-only, or you need a worst-case guarantee, use the heap. This comparison is the usual follow-up question for LC 215.
Extra: median of medians gives a guaranteed O(n)
Quickselect is O(n²) in the worst case. There is an algorithm called median of medians (also known as BFPRT) that chooses the pivot carefully enough to make the worst case O(n) as well. Its constant factor is large, so in practice randomized quickselect is faster. It is worth knowing that it exists and being able to name it; for real code and for contests, randomization is the practical choice.
Worked example C · merge intervals: sorting turns the problem around
MEDIUMLC 56 — sorting is not the goal; it turns "overlapping" into "next to each other".
Problem: given a list of intervals such as [[1,3],[2,6],[8,10],[15,18]], merge the ones that overlap and return the resulting non-overlapping intervals. Brute force: compare every pair, merge, and repeat — O(n²), and the chain reaction (a merged interval now overlaps something else) is hard to handle correctly. Why it can be improved: in random order, two intervals that can be merged may sit anywhere in the list. But once the intervals are sorted by left endpoint, intervals that can be merged are always next to each other. The reason: every later interval has a left endpoint that is greater than or equal to the current one. So it either overlaps the current merged interval (its left endpoint is ≤ the current right endpoint) or it starts strictly after it. A later interval can never reach back past an interval that did not overlap.
So after sorting in O(n log n), one linear scan is enough: keep the right endpoint of the current merged interval; if the next interval connects, extend that right endpoint; if it does not, close the current interval and start a new one. Step through it:
Three implementations. Both do the same two things: sort by left endpoint and compare the next left endpoint with the current right endpoint.
key=lambda x: x[0] is still the better form. It states the sort key directly, and the key is computed once per element instead of on every comparison."Sort first, then scan once" solves a whole family of problems
Meeting rooms (LC 253), minimum number of arrows to burst balloons (LC 452), non-overlapping intervals (LC 435), merge intervals (LC 56) — for interval problems the first move is almost always sort by the left endpoint or by the right endpoint. That turns a question about any two intervals into a question about two neighboring intervals, which one pass can answer. The same pattern, sorting as preparation and scanning to decide, is used throughout chapter 6 on greedy algorithms, where sorting is also the first step of most solutions.
Problem set: nine sorting problems
Core setOrdered by idea: counting, merging, comparators, partition variants, then merge sort. Think for 30 seconds before opening a hint.
Quiz
✎ QuizAnswer all 8 correctly to mark this chapter as complete.
Why does any comparison-based sort need at least Ω(n log n) comparisons in the worst case?
Which of these four sorts is stable — that is, elements with equal keys keep their original relative order?
What is the average time complexity of quickselect for finding the kth largest element? (Use the O(...) form, such as O(n) or O(n log n).)
After one pass of the quicksort partition, what is true about the pivot element?
Which statements about counting, bucket, and radix sort (the non-comparison sorts) are correct? Select all that apply.
LC 179, largest number: build the largest integer from [3, 30, 34, 5, 9]. Which comparison rule is correct?
On an array that is already nearly sorted, what is the best-case time complexity of insertion sort?
An interviewer asks you to choose between quickselect and a heap of size K for LC 215. Which statement of the trade-off is the most accurate?
- Sorting is often not the goal but the preparation. Binary search, removing duplicates, merging intervals, and most greedy algorithms only work on sorted data. When a problem gives you unordered input and asks about relationships between items, ask first what sorting would change.
- The three O(n²) sorts differ by their loop invariant. Bubble and selection fix one element in its final position per round; insertion only keeps the first i elements sorted among themselves. Insertion sort is O(n) on nearly sorted data and is the best of the three for small arrays.
- Merge sort: split, recurse, merge. O(n log n) in the best, average, and worst case, stable, O(n) auxiliary space. It is the choice for linked lists, for external sorting, and whenever stability is required.
- Quicksort is built on partition: one pass places the pivot at its final index, for good. Fastest on average, but O(n²) in the worst case, so it needs a random pivot (sorted input with a fixed pivot is the bad case) and a three-way partition when there are many duplicates. Running the same partition but searching only one side is quickselect (LC 215).
- The Ω(n log n) lower bound applies to comparison-based sorting only, and the decision-tree argument is the proof. Counting, bucket, and radix sort do not compare; they use the value range instead, which gets counting sort to O(n + k) and radix sort to O(d(n + k)). The condition is what matters: the keys must map to a bounded range of integers or to buckets.
- Stable means equal elements keep their original relative order, which is what lets you apply sorts one after another: sort by the secondary key, then by the primary key with a stable sort. Merge, insertion, and bubble sort are stable; quicksort, heap sort, and selection sort are not.
- Built-in sorts combine several algorithms. Java uses dual-pivot quicksort for primitives (not stable, but that cannot be observed on primitives) and TimSort for objects (stable). Python uses TimSort and is stable. JavaScript has been required to be stable since ES2019, but with no comparator it compares elements as strings, so
[1, 10, 2].sort()returns[1, 10, 2]. Always pass a comparator for numbers.