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.
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.
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²).
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.