Skip to content
BENIBIX Learn

Merge Sort vs Quicksort

Merge sort and quicksort are both fast, but they differ. Merge sort is always O(n log n) and needs extra memory. Quicksort sorts in place and is often faster, but bad pivots make it slow.

Development🧮 Algorithms & Data Structures

Merge Sort

A sort that splits the list in halves, sorts them, then merges them back.

Merge sort splits a list in half, sorts each half, then merges the two halves. It keeps splitting until each piece has one item, which is already sorted. Merging two sorted lists is quick, because you only compare their front items. It always takes O(n log n) steps, even in the worst case. It needs extra memory the size of the list.

Example
Lucy merge-sorts 8 numbers. They split into 8 single items, then merge into pairs, fours and one sorted list of 8.
Why it matters
Its speed never gets bad, and it keeps equal items in their first order. Many built-in sorts use its ideas.
Full entry
Development🧮 Algorithms & Data Structures

Quicksort

A fast sort. It splits items around a pivot, then sorts each side.

Quicksort picks one item, called the pivot, and puts smaller items to its left. Larger items go to its right. Then it does the same to each side, until every piece is sorted. It sorts in place, so it needs little extra memory. On average it takes O(n log n) steps and is very fast in practice. With a bad pivot every time, it slows to O(n²).

Example
Emma's quicksort picks 5 as the pivot for 8, 3, 5, 9, 1. It moves 3 and 1 left and 8 and 9 right, then sorts each side.
Why it matters
It is one of the fastest sorts in real use, and many built-in sorts start from it.
Full entry

In one line

Merge Sort
A sort that splits the list in halves, sorts them, then merges them back.
Quicksort
A fast sort. It splits items around a pivot, then sorts each side.