Merge sort is a stable sorting algorithm, meaning it preserves the original order of items that have the same value

When you sort a list using merge sort, items with identical sort keys stay in the same relative position they had before the sort. If you have two records with the name "Smith" and the first one appeared before the second in your original list, it will still appear first after merge sort finishes. This matters when you're sorting by one field but want to preserve the order from a previous sort, or when the order of equal items carries meaning in your data.

Merge sort achieves this stability through the way it combines sorted sublists. During the merge step, when two items have equal values, the algorithm always takes the item from the left sublist first. Since the left sublist contains items that appeared earlier in the original list, this choice preserves their original order.

Key Takeaways

  • Merge sort maintains the original order of items with equal values, which makes it useful for multi-level sorting or preserving meaningful orderings.
  • The stability comes from the merge step: when values are equal, the algorithm takes the item from the left sublist before the right sublist.
  • Not all sorting algorithms are stable — quicksort and heapsort can rearrange equal items, while insertion sort and bubble sort are also stable.
  • Stability matters most when you're sorting data multiple times or when the relative order of equal items has meaning in your application.

How the merge step preserves order

The merge step is where merge sort's stability lives. When you have two sorted sublists and need to combine them into one sorted list, you compare items from each list one at a time. Whichever item is smaller goes into the result first. The key rule: if both items are equal, you always take from the left sublist.

This rule matters because of how merge sort divides the original list. The left sublist contains items that appeared earlier in the original data. By always preferring the left sublist when values tie, merge sort ensures that earlier items stay earlier. If the algorithm instead took from the right sublist when values were equal, it would reverse the order of equal items, making the sort unstable.

Here's a concrete example: suppose you have student records sorted by name, and you want to sort them by grade while keeping students with the same grade in alphabetical order. If Alice and Anna both have an A, and Alice appeared first in your alphabetically-sorted list, merge sort will keep Alice first after sorting by grade. An unstable sort might put Anna first, losing the alphabetical ordering you had built in.

Stable versus unstable sorting algorithms

Stable algorithms preserve the order of equal items. Besides merge sort, insertion sort and bubble sort are stable. These algorithms tend to be slower on large datasets but are useful when order matters. Counting sort and radix sort are also stable, though they work differently than comparison-based sorts.

Unstable algorithms do not may provide the order of equal items. Quicksort, heapsort, and selection sort are all unstable. They are often faster than stable sorts, especially on large datasets, but you cannot rely on them to preserve a previous ordering. If you use quicksort to sort by grade, students with the same grade might end up in any order, even if they were alphabetical before.

The choice between stable and unstable depends on your data and what you're trying to do. If you only care about the final sort order and speed matters, an unstable sort is fine. If you're doing multiple sorts or the relative order of equal items is meaningful, stability becomes important.

When stability actually matters in practice

Stability is most useful when you sort data in stages. Imagine a spreadsheet where you first sort by department, then by salary within each department. If you use a stable sort for the second operation, employees with the same salary stay in department order. An unstable sort might scramble them.

Another real case: search results. If a search engine ranks results by relevance score, many results might have the same score. A stable sort keeps those equal-scoring results in their original order — perhaps the order they were added to the index, or the order they appeared on the page before. An unstable sort could shuffle them randomly each time you search, making the results feel inconsistent.

Stability also matters when you're sorting records that contain multiple fields and you want to preserve a meaningful secondary order. Database queries often rely on stable sorts to maintain consistent results across multiple queries.

The performance cost of stability

Merge sort uses extra memory to achieve stability — it needs space to hold the sublists while merging them. This extra space is why merge sort requires O(n) additional memory, where n is the size of the list. Quicksort, by contrast, can sort in place with only O(log n) extra space, making it faster on systems where memory is limited.

The time complexity of merge sort is O(n log n) in all cases — best, average, and worst. Quicksort is also O(n log n) on average but can degrade to O(n²) in the worst case, though this is rare with good pivot selection. For most practical purposes, the memory overhead of merge sort is the real trade-off, not the time.

If you need stability and speed, you might use a hybrid approach: sort with an unstable algorithm, then use a stable sort as a final pass to organize equal items. Or you might add a secondary sort key — like the original position — to make the sort deterministic even with an unstable algorithm.

How to tell if your sorting algorithm is stable

The documentation for a sorting function should state whether it's stable. In Python, the built-in sorted() function and the list.sort() method are both stable — they use Timsort, a hybrid algorithm that preserves order. In JavaScript, the stability of Array.sort() is now may provide by the ECMAScript standard, though older browsers may not follow this.

In Java, Arrays.sort() for objects is stable, but Arrays.sort() for primitives is not. C++'s std::stable_sort() is explicitly stable, while std::sort() is not. If you're unsure, check the language documentation or test it yourself by sorting a list of objects with equal keys and seeing whether their original order is preserved.

When you're writing your own sort or choosing between library functions, ask: do I need the order of equal items to stay the same? If yes, use a stable sort or add a tiebreaker field. If no, you can use whatever is fastest.

Frequently Asked Questions

Can I make an unstable sort stable by adding a tiebreaker?

Yes. If you add the original position as a secondary sort key, any algorithm will produce stable results. This is how databases often handle it — they sort by the requested column, then by row ID to break ties. The downside is extra work during the sort, but it works with any algorithm.

Is merge sort always the best choice if I need stability?

Not necessarily. Python's sorted() and list.sort() use Timsort, which is stable and faster than merge sort on real-world data because it takes advantage of existing order. If you're working in a language where Timsort is available, use it. Merge sort is stable and reliable, but not always the fastest stable option.

What happens if I sort the same list twice with an unstable algorithm?

The final result will be correctly sorted, but the order of equal items might differ between runs. If you sort by grade with quicksort, then sort by name with quicksort, students with the same name might not stay in grade order. The second sort scrambles the order the first sort created.

Does stability matter for sorting numbers?

Only if the numbers represent something where order matters. If you're sorting pure numerical values and don't care about ties, stability is irrelevant. But if those numbers are IDs or codes where the original sequence has meaning, or if you're sorting records that happen to have the same numerical value, stability becomes important.