What are sorting algorithms?
A sorting algorithm rearranges a list into order — for numbers, usually smallest to largest — by comparing, swapping, shifting or counting its elements. Sorting algorithms differ in speed (O(n²) simple sorts, O(n log n) merge and quick sort, O(n + k) counting sort), in the extra memory they need and in whether they are stable. This visualizer animates eight of them step by step and races them side by side in Compare mode.
The three families of sorting algorithms
- Simple sorts — bubble, selection, insertion. Two nested loops that fix one element or one pair at a time: O(n²) on average, but tiny, in-place and, for insertion sort, very fast on nearly sorted data. Shell sort runs insertion sort over shrinking gaps and lands between O(n²) and O(n log n).
- Divide and conquer — merge sort and quick sort. Split, solve the parts recursively, combine. Both average O(n log n): merge sort does its real work when combining, quick sort when splitting.
- Non-comparison sorts — counting and radix sort. They never ask “is a < b?” but use the keys as array indices, so they run in linear time on integers with a small range or few digits.
The table at the bottom of this page lists each algorithm's time as best · average · worst case.
Which sorting algorithm should you use?
- General-purpose, in memory: quick sort with a random or median-of-three pivot — the fastest on average.
- Stability or a guaranteed O(n log n): merge sort, also the natural choice for linked lists and data too big for memory.
- Small or nearly sorted arrays: insertion sort, whose cost is O(n + inversions).
- Integers from a small range (scores, ages, bytes): counting sort, O(n + k).
- Many fixed-width keys (32-bit integers, IDs, dates): radix sort, O(d·(n + b)).
- Tiny code, no recursion, no extra memory: shell sort.
Real libraries combine these ideas. Python's sorted(), Java's object sort and V8's Array.prototype.sort use Timsort (merge sort plus insertion sort on short runs); C++ std::sort is introsort, a quick sort that falls back to heap sort on deep recursion and finishes small ranges with insertion sort.
Stable vs unstable, in-place vs out-of-place
A sort is stable if equal keys keep their original order. That matters when you sort by several fields: sort students by name, then stably by grade, and students with the same grade stay alphabetical. Bubble, insertion, merge, counting and radix sort are stable; selection, shell and quick sort are not, because their long jumps can carry one copy of a value past another.
A sort is in-place if it needs only O(1) extra memory (quick sort's O(log n) stack is conventionally included). Merge sort needs an O(n) buffer, counting sort a count array and an output array, radix sort its buckets. In the visualizer, the Dupes preset tags repeated values *a*, *b*, … so you can watch which algorithms keep them in order.
Compare mode: race the algorithms
The Step-by-step view explains one algorithm at a time with pseudocode, live variables and counters. Compare races up to nine algorithms on four inputs of the same size — random, nearly sorted, reversed and few unique — on a shared clock where each comparison or write costs one tick, so it measures work, not hardware. Watch for:
- Insertion sort wins the nearly sorted row by a wide margin, yet is one of the slowest on reversed input.
- Quick sort with a last-element pivot is fast on random input but slides towards O(n²) on nearly sorted and reversed input; add the median-of-three variant to see the fix.
- Merge sort takes almost the same number of ticks on every row.
- Counting and radix sort ignore the input order; with the race's two-digit keys they beat every comparison sort on random, reversed and few-unique input.
Time and space complexity
| Case | Time | Space | Why |
|---|---|---|---|
| Bubble sort | O(n) · O(n²) · O(n²) | O(1) | Stable, in-place. O(n) best case needs the early-exit check. |
| Selection sort | O(n²) · O(n²) · O(n²) | O(1) | Not stable, in-place. At most n − 1 swaps. |
| Insertion sort | O(n) · O(n²) · O(n²) | O(1) | Stable, in-place. Cost grows with the inversions. |
| Shell sort | O(n log n) · ≈ n^1.25–1.5 · O(n²) | O(1) | Not stable, in-place. Depends on the gaps. |
| Counting sort | O(n + k) in every case | O(n + k) | Stable, not in-place. k = range of the values. |
| Radix sort (LSD) | O(d·(n + b)) in every case | O(n + b) | Stable, not in-place. d digits in base b. |
| Merge sort | O(n log n) in every case | O(n) | Stable, not in-place. No bad inputs. |
| Quick sort | O(n log n) · O(n log n) · O(n²) | O(log n) | Not stable, in-place. Bad pivots cause the worst case. |
Frequently asked questions
Which sorting algorithm is the fastest?
For general data in memory, a well-tuned quick sort or a hybrid such as introsort is usually fastest. Timsort wins on partly sorted data, and counting or radix sort beat both on small integer keys — no single sort is fastest on every input.
Which sorting algorithms are stable?
Bubble, insertion, merge, counting and radix sort are stable. Selection, shell, quick and heap sort are not.
What is the difference between O(n²) and O(n log n) sorting?
For 1,000 elements, n² is a million steps while n log₂ n is about 10,000. Quadratic sorts are fine for a few dozen items but unusable on large inputs.
Can a sorting algorithm be faster than O(n log n)?
Not with comparisons alone: n elements have n! possible orders, and telling them apart takes at least log₂(n!) ≈ n log₂ n comparisons. Counting and radix sort run in linear time because they index arrays with the keys instead of comparing them.
What sorting algorithm does Python use?
list.sort() and sorted() use Timsort, a stable merge sort / insertion sort hybrid that detects already-sorted runs, so nearly sorted input sorts in close to linear time.
Keep learning
- Merge Sort VisualizerMerge sort splits the array in half, sorts each half recursively and merges the sorted halves, in O(n log n) time. Watch every split and merge animated.
- Quick Sort VisualizerQuick sort picks a pivot, moves smaller values left and larger ones right, then recurses: O(n log n) on average. Watch Lomuto and Hoare partitioning animated.
- Insertion Sort VisualizerInsertion sort takes each element and slides it left into place in the sorted prefix. Watch every shift animated, with Python code and O(n²) complexity.
- Bubble Sort VisualizerBubble sort repeatedly swaps adjacent out-of-order elements until a pass makes no swaps. Watch it step by step, with Python code and O(n²) complexity explained.
- Selection Sort VisualizerSelection sort finds the smallest unsorted element and swaps it to the front, one position per pass. See every comparison animated, with code and complexity.
- Shell Sort VisualizerShell sort runs insertion sort on elements a gap apart, shrinking the gap to 1 so values move far in one jump. Watch every gap pass animated, with Python code.
- Counting Sort VisualizerCounting sort sorts integers in O(n + k) time by counting each value and placing elements with prefix sums, with no comparisons. Watch every phase animated.
- Radix Sort VisualizerRadix sort orders integers digit by digit — ones, then tens, then hundreds — using stable bucket passes. Watch LSD radix sort animated, with Python code.
- Heap Sort VisualizerHeap sort visualizer: build a max-heap, then swap the root to the end and sift down, step by step. O(n log n) worst case, in place but not stable, with code.
Last updated