# Merge Sort vs Quicksort

URL: https://softwaredictionary.org/compare/merge-sort-vs-quicksort
Last updated: 2026-09-30

In short: Merge sort guarantees O(n log n) time but uses extra memory, while quicksort partitions around a pivot in place and is usually faster, but can slow to O(n²).

## What is the difference between merge sort and quicksort?

Merge sort and quicksort are both divide-and-conquer sorting algorithms: they break the problem into smaller pieces, solve those and combine the results. Merge sort splits the list into two halves, sorts each one recursively and then merges the two sorted halves. Quicksort picks a pivot element, partitions the list so smaller items go left and larger items go right, and then sorts each side.

They put the hard work in different places. Merge sort's split is trivial and its merge step does the work, which always takes O(n log n) time but needs O(n) extra memory on arrays. Quicksort's partition step does the work in place, using little extra memory and running very fast on average, but if the pivots are consistently poor, such as always the smallest item, it slows to O(n²).

Real-world sort functions often combine them with other algorithms. Introsort starts with quicksort and switches to heapsort if the recursion gets too deep, while Timsort-style algorithms, used in Python and in Java for objects, are built on merge sort and insertion sort.

A common misconception is that quicksort is always the best choice. It is fast on average for arrays in memory, but merge sort is stable (equal items keep their original order), has a guaranteed worst case and suits linked lists and data too large to fit in memory.

| Aspect | Merge Sort | Quicksort |
| --- | --- | --- |
| Strategy | Split in half, sort each half, then merge | Partition around a pivot, then sort each side |
| Average time | O(n log n) | O(n log n), usually faster in practice |
| Worst-case time | O(n log n), guaranteed | O(n²) with consistently bad pivots |
| Extra memory | O(n) for merging arrays | O(log n) for recursion; sorts in place |
| Stability | Stable: equal items keep their order | Not stable in typical implementations |
| Works well on | Linked lists and data too large for memory | Arrays in memory, thanks to good cache use |

## Choose Merge Sort when

- You need a stable sort that keeps equal items in order.
- A guaranteed worst case matters more than average speed.
- You are sorting a linked list or data stored on disk.

## Choose Quicksort when

- You are sorting arrays in memory and want top average speed.
- Extra memory is limited.
- Stability does not matter for your data.

## Frequently asked questions

**Which is faster, merge sort or quicksort?**

Quicksort is usually faster for arrays in memory because it works in place and uses the CPU cache well. Merge sort wins when you need a guaranteed O(n log n) worst case or are sorting linked lists or very large data.

**Is quicksort stable?**

Not in its usual in-place form, so equal items may change order. Merge sort is stable, which matters when you sort records by one field and then by another.

**Why does quicksort have an O(n²) worst case?**

If the pivot is always the smallest or largest item, each partition removes only one element, so the recursion goes n levels deep. Choosing random or median-of-three pivots makes this very unlikely.

---

Software Dictionary: https://softwaredictionary.org/ · https://softwaredictionary.org/llms.txt