Sorting algorithms compared

There is no single fastest sorting algorithm. Some are simple but slow, some are fast on random data but stumble on sorted data, and some are not comparison sorts at all. Racing all eight on the same list shows the differences at a glance.

Eight lanes of bars, one per sorting algorithm, some already sorted and green while others are still unsorted
Eight lanes of bars, one per sorting algorithm, some already sorted and green while others are still unsorted

Three families

Bubble, selection and insertion sort are the simple sorts. They compare and swap values close together and need time proportional to n² on a random list. Merge, quick and heap sort divide the work cleverly and need time proportional to n log n, which is the best any sort can do when all it may ask is which of two values is larger. Radix and counting sort skip that question altogether: they use the digits or values themselves, which only works for keys like small whole numbers.

Measuring the work

The sort match counts one operation for every comparison, every digit or value read, and every swap or move. On 40 random values that comes to about 120 for counting sort, 240 for radix sort, 260 for quicksort, 380 for merge sort, 490 for heap sort, about 820 each for selection and insertion sort, and over 1,100 for bubble sort. Real computers also care about memory: quicksort is usually faster in practice than its count suggests, and heap sort slower, because of how they move through the list.

The input matters

On a nearly sorted list, insertion sort needs only about 50 operations for 40 values and bubble sort about 90, because each value is close to its place. On a reversed list the same two need 1,560, their worst case. Selection, heap, merge, radix and counting sort hardly care about the order. Quicksort with the median of three handles sorted and reversed lists well, but with a naive pivot a sorted list is its worst case. Few unique values slow quicksort down, because equal values all go to one side.

Memory and stability

Bubble, selection, insertion, quick and heap sort work in place, with little or no extra memory. Merge, radix and counting sort need a buffer as long as the list. A stable sort keeps equal values in their original order: bubble, insertion, merge, radix and counting sort are stable, while selection, quick and heap sort are not. Stability matters when you sort records by one field after another.

Which one to use

In practice you use the sort built into your programming language: usually Timsort, a merge sort that uses insertion sort for short pieces and is fast on partly sorted data, or introsort, a quicksort that falls back to heap sort and uses insertion sort for small parts. For many small integer keys, counting or radix sort can beat both. Bubble and selection sort are mostly teaching tools.

Explore it

Open the sort match and press Play. Each lane is one sort on the same list; the number on the right counts its operations, and a lane turns green when it is done. Try a nearly sorted list, a reversed one and few unique values, and watch the finishing order change. Each sort also has its own app, where you can step through it in detail.

Frequently asked questions

What is the fastest sorting algorithm?

For general data, quicksort and merge sort (and hybrids built on them, like introsort and Timsort) are the fastest on average, at n log n. For small integer keys, counting and radix sort are faster still. For short or nearly sorted lists, insertion sort wins.

Why can no comparison sort beat n log n?

A list of n values can be in n! orders, and each comparison has two outcomes, so at least log₂(n!) comparisons are needed to tell them all apart in the worst case. That is about n log₂ n. Radix and counting sort avoid this limit because they do not compare.

Which sorting algorithms are stable?

Bubble, insertion, merge, radix and counting sort are stable in their usual forms. Selection sort, quicksort and heap sort are not, because they move values over long distances.

Which sorts need extra memory?

Merge, radix and counting sort need a buffer about as long as the list. Bubble, selection, insertion and heap sort need almost none, and quicksort only a little for its recursion.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Start the sort match