At a glance
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
What the race shows
- Input order matters as much as the algorithm. On nearly sorted data, insertion sort finishes in about n steps and beats merge sort easily. On reversed data it does about n²/2 swaps and loses badly.
- Quicksort’s worst case is real. With the last element as the pivot, sorted and reversed input both make it quadratic.
- Merge sort never surprises you. Its operation count barely changes with the input order. That predictability is why library sorts build on it.
- Bubble sort rarely wins. It does the same swaps as insertion sort, plus extra comparisons.
Choosing a sort
- In real code, use the built-in sort. It is tuned, tested and protected against bad inputs.
- Need equal items to keep their order? Use a stable sort: merge sort or Timsort.
- Data almost sorted already, or very small? Insertion sort is hard to beat.
- Memory tight? Quicksort or heapsort sort in place.
Write your own
The editor below runs your own sort(a) on the bars, in JavaScript or Python. Every read (a[i]) and write (a[i] = x) shows up in the figure, so you can watch your algorithm work and count its cost. Change the size or input to run it again on new data.
Define sort(a). Run with Ctrl+Enter or ⌘+Enter. Tab indents; press Esc, then Tab, to leave the editor.
Press Play or Step to start.
0 comparisons0 swapsstep 0 / 00 / 16 in placecomparingmovingpivot
Your code runs in a separate worker in your browser. It never leaves your computer, and a loop that never ends is stopped after a few seconds. Python takes a moment to load the first time.
Check yourself
Check yourself
On nearly sorted input, which usually needs fewer operations?
Each value in nearly sorted data only moves a step or two, so insertion sort does about n operations. Merge sort still does about n log₂ n.
Check yourself
Which of these sorts is not stable?
Quicksort’s long-distance swaps can reorder equal values. Merge and insertion sort never move a value past an equal one.
Sources
- Donald Knuth, The Art of Computer Programming, Vol. 3, chapter 5, “Sorting.”
- Tim Peters, “listsort.txt,” the design notes for Python’s sort, in the CPython source.
Finished this page?
Your list