Sorting algorithm time complexity
| Algorithm | Best | Average | Worst | Memory | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| 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 |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Big O notation describes how the number of operations grows with the input size n in the limit. With n = 1,000, n² is a million while n·log₂n is about 10,000: that is why quadratic algorithms only pay off on small arrays.
What to watch in the animation
- Bubble and insertion sort finish almost instantly on nearly sorted data: their best case is linear.
- Selection sort always makes the same n(n−1)/2 comparisons whatever the data, but at most n − 1 swaps.
- Quicksort with the last element as pivot becomes quadratic on sorted or reversed data. Real implementations avoid it with a random pivot or median-of-three.
- Merge sort makes almost the same number of comparisons on any input.
- Heap sort first seems to scramble the array while building the heap, then fixes the largest values at the end one by one.
Press "Count comparisons for all" to see these differences in numbers for the size you chose.
What does it mean for a sorting algorithm to be stable?
An algorithm is stable if two elements with the same key keep their relative order. It matters when you sort by several criteria: if you sort a class list by name and then, with a stable algorithm, by grade, students with the same grade stay in alphabetical order.
Frequently asked questions
Which algorithm do programming languages use?
None of these exactly. Python and Java (for objects) use Timsort, a stable hybrid of merge sort and insertion sort. C++ uses introsort, which starts as quicksort, switches to heap sort if recursion gets too deep, and uses insertion sort for small ranges.
Can you sort faster than n log n?
Not by comparing elements: it is proven that any comparison sort needs Ω(n log n) in the worst case. Algorithms such as counting sort or radix sort beat it because they do not compare; they exploit the fact that keys are bounded integers.
Why count comparisons and writes?
They are the operations that dominate the cost. Counting them lets you compare algorithms independently of your computer's speed. Here a swap counts as two writes.
More computer science tools
Two's Complement Calculator
Signed integers in two's complement, one's complement and sign-magnitude, plus overflow.
OpenIEEE 754 Floating-Point Converter
32 and 64-bit floating point with biased exponent and rounding error.
OpenKarnaugh Map Solver
Minimal SOP and POS expressions with the groups highlighted on the map.
OpenIPv4 Subnet Calculator
Network, broadcast, hosts, wildcard and VLSM planning with the binary AND.
OpenTruth Table Generator
Truth table for any expression, with minterms and canonical forms.
OpenNumber Base Converter
Binary, octal, decimal, hex and bases 2–36 with repeated division.
Open