Which sorting algorithm is fastest?

It depends on the data. Quicksort is usually fastest in practice for arrays due to cache locality, averaging O(n log n), but can degrade to O(n²) on bad pivots. Mergesort and heapsort guarantee O(n log n) worst case. For small integer keys, counting or radix sort run in linear time.

What does a stable sort mean?

A stable sort preserves the relative order of elements with equal keys. This matters when you sort by one field and then another — a stable sort keeps the earlier ordering as a tiebreak. Mergesort, insertion sort and Timsort are stable; quicksort and heapsort are not.

Why can't comparison sorts beat O(n log n)?

Any sort that only compares pairs of elements must distinguish all n! possible orderings, which requires at least log₂(n!) ≈ n log n comparisons. This is a proven lower bound, so quicksort, mergesort and heapsort cannot do better in the worst case.

When should I use radix or counting sort?

Use them when keys are integers (or fixed-width strings) within a bounded range. They avoid comparisons and run in linear O(n + k) time, but need extra memory proportional to the key range and only work on data with that structure, not arbitrary comparable objects.

Does this reference send my searches anywhere?

No. Filtering and sorting happen entirely in your browser. Nothing you type is uploaded, logged or stored.

Sorting Algorithm Reference

Email me this result

Get this tool's output sent to your inbox, plus one useful tool a week. No spam, unsubscribe any time.

Choosing the right sort

No single sorting algorithm wins everywhere — the right choice depends on data size, distribution, memory limits and whether you need stability. This reference puts the common algorithms side by side with their best, average and worst-case time complexity, space cost and stability, so you can pick deliberately. Search by keyword or sort the table by any complexity column.

How it works

Algorithms split into comparison sorts and non-comparison sorts:

Comparison sorts (≥ O(n log n) worst case):
  Quick   avg O(n log n), worst O(n²), in-place, unstable
  Merge   O(n log n) always, stable, needs O(n) extra space
  Heap    O(n log n) always, in-place O(1), unstable
  Timsort O(n) best, O(n log n) avg, stable (Python/Java default)

Non-comparison sorts (linear, bounded keys):
  Counting O(n + k)        Radix O(d(n + k))        Bucket O(n + k) avg

Comparison sorts have a proven O(n log n) lower bound because they must distinguish all n! orderings. Non-comparison sorts beat it by exploiting integer key structure, trading memory and generality for speed.

Tips and example

For general-purpose array sorting, a tuned quicksort (randomised or median-of- three pivot) is usually fastest; standard libraries often use Timsort or introsort under the hood.
Need stability or worst-case guarantees? Use mergesort or Timsort.
Sorting nearly-sorted data? Insertion sort and Timsort approach O(n).
Tight on memory with a worst-case guarantee required? Heapsort sorts in place in O(1) extra space, at the cost of cache locality and stability.