Sorting algorithm visualizer

Each bar is one value; its height is the value. Pick an algorithm, an input shape and a size, then press Play, or Step through one operation at a time. Every operation is one of three things: a comparison of two values, a write that changes the array (a swap is two), or the moment a position receives its final value. The counters at the top count them as the algorithm goes.

The table beside the bars runs all six algorithms on the same array, so the comparison is fair. Try these:

• At 96 values on random input, compare the counts: the quadratic sorts need thousands of comparisons, the n log n sorts a few hundred, and merge sort comes closest to the lower bound.
• Switch to Nearly sorted. Insertion and bubble sort drop to little more than one comparison per value, because they only do work for pairs that are out of order.
• Switch to Reversed and watch quicksort. It takes the last element as its pivot, which here is always the smallest or largest value left, so every partition is lopsided and it does as many comparisons as selection sort.
• Try Few distinct values with quicksort and heapsort, then insertion and merge sort, and look at the Stable row: equal values keep their order only in the stable sorts.

The algorithms run on a copy of the array while every comparison and write is recorded, and the animation replays that record. Tests check that every algorithm sorts, that the stable ones are stable, that counts on sorted and reversed input match the textbook formulas, and that every algorithm's average stays above the lower bound.

A sorting algorithm arranges a list of items in order: numbers from smallest to largest, names alphabetically, orders by date. Most sorting algorithms are comparison sorts: they learn about the data only by asking whether one item comes before another, and they rearrange it based on the answers. That makes them work for any kind of item, as long as there is a rule for comparing two.

The cost of a comparison sort is usually measured in comparisons, and sometimes in moves or writes. What matters is how that cost grows with n, the number of items. Sorting a thousand items by the obvious method, repeatedly picking the smallest remaining one, takes about half a million comparisons. A million items would take about five hundred billion. Merge sort, quicksort and heapsort need about n log₂ n comparisons instead, around twenty million for a million items.

Sorting matters well beyond putting lists in order. Searching a sorted list with binary search takes log₂ n steps instead of n, duplicates end up next to each other, and databases sort to join tables, group rows and build indexes.

Bubble sort

Bubble sort walks along the array comparing neighbours and swapping any pair that is out of order. Each pass carries the largest remaining value to the end, like a bubble rising. The version here remembers where the last swap of each pass happened, since everything after it is already in place, so a sorted array takes a single pass. Each swap fixes exactly one inversion (one pair out of order), so its writes are always twice the number of inversions.

Selection sort

Selection sort finds the smallest value in the unsorted part and swaps it to the front, then repeats on the rest. It always makes n(n − 1)/2 comparisons, whatever the input, but at most n − 1 swaps, which made it attractive when writing to memory was expensive. The long-distance swap makes it unstable.

Insertion sort

Insertion sort keeps a sorted prefix and inserts each new value into it by shifting larger values one place right. It makes one comparison per inversion plus at most one per value, so it is fast on data that is almost in order, and it is the fastest of all on very small arrays. Library sorts switch to it for short pieces, typically a few dozen items or fewer.

Merge sort

Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves by repeatedly taking the smaller front value. Merging two halves of n items takes at most n − 1 comparisons, and there are log₂ n levels of halving, so it never needs more than about n log₂ n. It is stable as long as ties are taken from the left half, but it needs a buffer as large as the array.

Quicksort

Quicksort picks a pivot, partitions the array into values smaller than the pivot and the rest, puts the pivot between them in its final place, and sorts the two sides recursively. This simulator uses the Lomuto partition with the last element as the pivot, the version in many textbooks. With good pivots the two sides are about equal and it needs about 2n ln n comparisons on average (exactly 2(n + 1)H_n − 4n, where H_n is the nth harmonic number). For 96 values that is 614, and the simulator averages 621 over 50 random arrays. With bad pivots it degrades to n², as the section on its worst case explains.

Heapsort

Heapsort arranges the array into a binary max-heap, where every parent is at least as large as its children, so the largest value is at the front. It then repeatedly swaps the front value to the end of the array, shrinks the heap by one, and sifts the new front value down to restore the heap. It guarantees O(n log n) with no extra memory, but makes about twice as many comparisons as merge sort and reads memory in a scattered pattern.

The first table gives the usual order-of-growth figures. The second counts what the simulator's implementations actually do, averaged over 50 random arrays of 96 values.

Any comparison sort can be drawn as a decision tree: each internal node is a comparison, its two branches are the two possible answers, and each leaf is a final ordering. The algorithm must reach a different leaf for each of the n! possible orderings of n distinct items, and a binary tree of depth d has at most 2^d leaves. So some input needs at least log₂(n!) comparisons, and the same argument applies to the average over all inputs.

By Stirling's approximation, log₂(n!) is about n log₂ n − 1.44n. For 96 items it is 499 comparisons; for a million items, about 18.5 million. Merge sort and heapsort reach O(n log n) in the worst case, so the bound is tight: no comparison sort can do asymptotically better, only improve the constant factor and the memory behaviour.

A sort is stable if items with equal keys keep their original order. Stability is what makes sorting by several fields in turn work: sort a list of orders by date, then stably by customer, and each customer's orders stay in date order. Sorts that swap items over long distances, like selection sort, quicksort and heapsort, are unstable; sorts that only move items past strictly larger ones, like insertion and merge sort, are stable. Languages often offer both: C++ has std::sort and std::stable_sort, and Rust has sort_unstable and sort.

A sort is in place if it needs only a small amount of memory beyond the array: heapsort needs O(1), quicksort O(log n) for its recursion when it recurses on the smaller side first. Merge sort needs an O(n) buffer. Stable in-place sorts exist, but they are complicated and slower, which is why library stable sorts usually allocate a buffer.

A sort is adaptive if it runs faster on input that is already partly in order. Insertion sort's cost tracks the number of inversions. Run-adaptive merge sorts such as Timsort find increasing or decreasing stretches already present in the data and merge them, so sorted, reversed and nearly sorted input take close to linear time. Real data is often like this: log records arrive almost in time order, and lists are often re-sorted after a few changes.

Quicksort is fast only if pivots split the array reasonably evenly. Taking the last element as pivot, as this simulator does, works well on random data but fails on input that is already sorted or reversed: the pivot is always the largest or smallest remaining value, one side of each partition is empty, and the recursion goes n levels deep. On 96 sorted values it makes 4,560 comparisons, n(n − 1)/2, against about 621 on random input.

Production quicksorts defend against this in three ways. Better pivots: the median of the first, middle and last elements, or of a larger sample, or a random element. Three-way partitioning, which groups values equal to the pivot so that input with many duplicates does not degrade. And introsort, from David Musser in 1997: if recursion goes deeper than about 2 log₂ n, switch to heapsort for that part, which caps the worst case at O(n log n). GNU's std::sort is an introsort. Pattern-defeating quicksort (pdqsort), by Orson Peters, adds detection of already-sorted runs and shuffles elements when it sees repeatedly bad partitions.

The lower bound applies only to algorithms that learn about the data by comparing. If keys are small integers, counting sort counts how many times each value occurs and writes them back in order, in O(n + k) time for k possible values. Radix sort applies a stable counting sort digit by digit, so fixed-width keys such as 32-bit integers sort in a few linear passes. Bucket sort spreads roughly uniform values into buckets and sorts each one. These are common where the keys suit them, for example on GPUs and in database engines, but they do not work for arbitrary comparable items, which is why general-purpose library sorts are comparison sorts.

Sorting was one of the first jobs given to computers, inherited from punched-card machines. Knuth credits John von Neumann with merge sort, in a 1945 program for the EDVAC. Tony Hoare devised quicksort in 1959, while a visiting student at Moscow State University working on machine translation, and published it in 1961 as Algorithm 64 in Communications of the ACM, with a fuller paper in 1962. J. W. J. Williams published heapsort, and the binary heap with it, in 1964, and Robert Floyd improved it the same year. Donald Knuth's The Art of Computer Programming, Volume 3: Sorting and Searching (1973) collected and analysed the field.

Later work turned to engineering. Jon Bentley and Douglas McIlroy's 1993 paper "Engineering a Sort Function" described a careful quicksort for the C library. Musser's introsort followed in 1997, Tim Peters wrote Timsort for Python in 2002, and Vladimir Yaroslavskiy's dual-pivot quicksort went into Java 7 in 2011. Orson Peters's pattern-defeating quicksort, published in 2021, is now the unstable sort in Go, and Rust replaced its sorts with driftsort and ipnsort in 2024.