Yes, merge sort is stable — it keeps equal items in their original order
A stable sort is one that preserves the original order of items that are equal according to the sorting rule. Merge sort is stable because of how it combines sorted lists: when two items have the same value, it always takes the one from the left list first, which maintains the sequence they had before sorting began.
This matters in real work. If you sort a list of people by last name, a stable sort keeps them ordered by first name within each last name group — because that was the order they were in before. An unstable sort might scramble the first names. For most everyday sorting tasks, you won't notice the difference. But when you're sorting data that already has a meaningful order you want to preserve, stability becomes the difference between correct and wrong.
Key Takeaways
- Merge sort is stable because it processes two sorted halves from left to right, always taking the leftmost equal item first.
- Stability means items with the same sort value stay in the order they were in before the sort happened.
- Other stable sorts include insertion sort and bubble sort; unstable sorts include quicksort and heap sort.
- You need stability when sorting data that already has a meaningful secondary order you want to keep.
How merge sort preserves order during the merge step
Merge sort works in two phases: divide the list in half, sort each half, then merge them back together. The stability happens in the merge. When you have two sorted lists side by side and need to combine them into one, you compare the first item from each list. Whichever is smaller goes into the result. If they're equal, merge sort always takes from the left list first.
That left-first rule is the key. Because you always pick the left item when values are equal, items that were originally on the left stay ahead of items that were originally on the right. The original sequence is preserved. If you changed the rule to "take from the right when equal," merge sort would become unstable — equal items would reverse their original order.
When stability actually matters in practice
Imagine a spreadsheet of employees with columns for department and hire date. You sort by department first, getting all the sales people together, all the engineers together. Now you want to sort by hire date within each department — the newest hires at the top. If you sort by hire date using a stable sort, the department grouping stays intact because items with the same hire date keep their original order. If you use an unstable sort, the departments might get scrambled.
Another example: sorting search results. A search engine might rank results by relevance score, but many results have the same score. A stable sort keeps those equal-scoring results in the order they were originally ranked — perhaps by how recently the page was updated. An unstable sort would shuffle them randomly, making the results feel less predictable to users.
In most programming work, though, you don't encounter this problem because you're sorting fresh data that has no meaningful prior order. Stability only matters when the data already has a sequence you want to keep.
Comparing merge sort to other sorting methods
| Sort Method | Stable? | Speed | When to use |
|---|---|---|---|
| Merge sort | Yes | O(n log n) always | When you need stability and consistent speed |
| Insertion sort | Yes | O(n²) average | Small lists or nearly sorted data |
| Bubble sort | Yes | O(n²) average | Teaching only; too slow for real work |
| Quicksort | No | O(n log n) average | Speed matters more than stability |
| Heap sort | No | O(n log n) always | may provide speed, stability not needed |
Merge sort is one of three common stable sorts. Insertion sort and bubble sort are also stable, but they're much slower on large lists. Quicksort and heap sort are faster than merge sort in many real situations, but they don't preserve order — they're unstable. The trade-off is usually between stability and speed, though merge sort gives you both at the cost of using extra memory to hold the two halves during merging.
The cost of stability: extra memory
Merge sort needs temporary space to hold the two halves while merging them. If your list has 1,000 items, merge sort creates temporary lists that together hold 1,000 items. This extra memory use is why some systems prefer quicksort or heap sort, which sort in place without needing extra space.
In modern programming, memory is usually cheap and plentiful, so this trade-off matters less than it did decades ago. Most languages' built-in sort functions use merge sort or a variant of it when stability is important, and quicksort or heap sort when speed and memory efficiency matter more. Python's built-in sort is stable. JavaScript's is stable in modern browsers. Java's sort for objects is stable, but its sort for primitive numbers is not.
How to tell if a sort is stable without reading the code
If you have a list of items with duplicate values and you sort it twice — first by one property, then by another — a stable sort will keep the first sort's order within groups of equal items in the second sort. An unstable sort will scramble it.
For example, sort a list of names by last name, then by first name. With a stable sort, people with the same last name stay ordered by first name. With an unstable sort, they might be in random order. You can test this yourself in any programming language by sorting a small list of objects with duplicate values and watching what happens to the secondary order.
Frequently Asked Questions
Does merge sort always produce the same result?
Yes. Merge sort is deterministic — the same input always produces the same output. Because it always takes from the left list when values are equal, there's no randomness. Other sorts like quicksort can vary depending on which item you pick as the pivot, making them less predictable.
Can you make merge sort unstable?
Yes. If you change the merge step to take from the right list when values are equal instead of the left, merge sort becomes unstable. The algorithm itself doesn't force stability — the implementation does. Most implementations keep it stable because that's usually what people want.
Is stability the same as being sorted correctly?
No. Both stable and unstable sorts produce a correctly sorted list according to the sorting rule. Stability is about what happens to items that are equal — whether they stay in their original order or get shuffled. A list can be correctly sorted and unstable at the same time.
Why don't all sorts use merge sort if it's stable and fast?
Merge sort uses extra memory, which matters when you're sorting huge amounts of data or working on a device with limited memory. Quicksort and heap sort are faster in practice on many real-world lists and don't need extra space. The choice depends on whether you need stability, how much memory you have, and how large your list is.