Open day and nightFree admissionPlease touch the exhibits

Room F1 · Computing

Watch six sorting algorithms race.

Run Bubble, Selection, Insertion, Merge, Quick and Heap Sort side by side. See every comparison and swap, then read why some scale to millions of items while others crawl.

How it works

Sorting means arranging items in order — smallest to largest, A to Z. Every algorithm below solves the same problem; they differ only in strategy, and strategy is what you are watching. Pick an algorithm (orRace mode for all six at once), choose an input, and press play. Bars light up as the engine works: yellow marks a comparison, red marks a move or swap, purple marks the pivot, and green marks positions that are finished.

The controls mirror a video player because the engine is one: play and pause with the space bar, step one operation at a time with the right-arrow key, restart with R, generate a new list with N, shuffle with S, and switch speeds from 0.25× to 8×. A code panel highlights each line of pseudocode as it executes, so the animation and the program stay in sync. Try the same race twice: once on a reversed list, once on an almost-sorted one, and watch Insertion Sort jump from the back of the pack to the front.

The six algorithms

Three of them are simple quadratic methods — easy to write, painful at scale. Three areefficient methods that reach O(n log n) with divide-and-conquer or a clever data structure. Each example below is complete, runnable Python operating on a plain list.

Bubble Sort — the neighbour swap

Walk along the list comparing neighbours and swapping any pair that is out of order. After each pass the largest unsorted item has “bubbled” to its final place, so the next pass can be one step shorter. If a full pass makes no swaps, the list is already sorted and the algorithm stops early — its one redeeming trait, giving O(n) on input that is already sorted.

def bubble_sort(a):
    n = len(a)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a

Selection Sort — pick the smallest, repeat

Divide the list into a sorted front and an unsorted rest. On each step, scan the whole unsorted rest for its minimum and swap it into place. It always performs the same number of comparisons — about n²/2 — no matter how sorted the input already is, which is why its best, average and worst cases are all O(n²). Its virtue is doing at most n swaps, once useful when swapping was expensive.

def selection_sort(a):
    n = len(a)
    for i in range(n):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

Insertion Sort — the card-player’s method

The way people sort playing cards: take the next item and slide it left past everything larger until it fits. On nearly sorted data almost nothing moves, so it runs in O(n) — the fastest method in the room for that case, and the reason real hybrid sorts use it for tiny sublists. On reversed data every item travels the full distance, hence O(n²) worst case. It is stable and needs no extra memory.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Merge Sort — divide, conquer, merge

Split the list in half, sort each half the same way (recursion bottoms out at single items, which are trivially sorted), then merge the two sorted halves by repeatedly taking the smaller front item. The split is always even, so every level costs O(n) and there are log n levels: O(n log n) guaranteed, in every case. The price is O(n) extra memory for merging, and it is stable — equal items never cross.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

Quick Sort — split around a pivot

Pick a pivot, then partition: everything smaller goes left, everything larger goes right. Sort each side the same way. When pivots land near the middle, the recursion is log n levels deep and the total is O(n log n) with tiny constants and only O(log n) extra memory for the recursion — usually the fastest in practice. When pivots land at an extreme, one side holds nearly everything and it degrades to O(n²). This simulator picks pivots by median-of-three (first, middle, last items), which makes the bad case rare on real data. The Python example below simply uses the last item as the pivot, to keep it short.

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p, i = a[hi], lo
        for j in range(lo, hi):
            if a[j] < p:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        quick_sort(a, lo, i - 1)
        quick_sort(a, i + 1, hi)
    return a

Heap Sort — a priority queue in disguise

Turn the list into a max-heap: a binary tree packed into the array where every parent is larger than its children, so the maximum sits at position zero. Repeatedly take the maximum, swap it to the end, shrink the heap by one, and restore the heap property by sifting down. Guaranteed O(n log n) with O(1) extra memory — but the jumping access pattern is unfriendly to processor caches, so it usually loses to Quick Sort and Merge Sort in wall-clock time despite matching them on paper.

def heap_sort(a):
    def sift(lo, n, i):
        while True:
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < n and a[lo + l] > a[lo + m]:
                m = l
            if r < n and a[lo + r] > a[lo + m]:
                m = r
            if m == i:
                return
            a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
            i = m
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift(0, n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift(0, end, 0)
    return a

Reading the table

Big-O describes growth, not stopwatch time: constants and hardware are deliberately ignored so theshape of scaling is visible. The table below is the standard reference (Cormen et al.,Introduction to Algorithms; NIST Dictionary of Algorithms and Data Structures). “Stable” means equal items keep their original order.

AlgorithmBestAverageWorstExtra spaceStable
Bubble SortO(n)O(n²)O(n²)O(1)Yes
Selection SortO(n²)O(n²)O(n²)O(1)No
Insertion SortO(n)O(n²)O(n²)O(1)Yes
Merge SortO(n log n)O(n log n)O(n log n)O(n)Yes
Quick SortO(n log n)O(n log n)O(n²)O(log n)No
Heap SortO(n log n)O(n log n)O(n log n)O(1)No

Try this in the simulator: race all six on a reversed list, then on an almost-sorted list. The finishing order flips — Insertion Sort goes from the back of the pack to the front — and no formula teaches that like watching it happen.

Three common mistakes

“Quick Sort is always the fastest.” On average it is among the fastest, but a simple Quick Sort has a worst case of O(n²), for instance when the pivot keeps landing at one end of the list. Merge Sort and Heap Sort stay at O(n log n) whatever the input.

“The simple quadratic methods are useless.” Insertion Sort is widely used for small lists and does very well on lists that are almost in order. Practical sorting routines are usually hybrids that switch to Insertion Sort for small pieces.

“A stable sort is one that never fails.” Stability means something precise: items with equal keys keep the order they had before sorting. Merge Sort and Insertion Sort are stable; Quick Sort and Heap Sort, in their usual forms, are not.

Questions visitors ask

Which sorting algorithm should I actually use in real code?

Almost always your language’s built-in sort: Python’s sorted(), JavaScript’s Array.sort() or Java’s Arrays.sort() for objects. They are engineered hybrids (Python and Java use Timsort) that run in O(n log n) time, are stable, and are tested by millions of users. The six algorithms here teach the ideas behind those tools, not replacements for them.

If Bubble Sort is slow, why is it still taught?

Because it is the simplest possible sorting idea: compare neighbours, swap if out of order, repeat. Watching it struggle next to Merge Sort in Race mode teaches more about O(n²) growth than any formula. Its early-exit optimisation also shows that the same algorithm can be O(n) on input that is already sorted and O(n²) in general.

What does it mean for a sort to be stable?

A stable sort keeps equal items in their original relative order. That matters when you sort by more than one key: sort a class first by name, then by grade with a stable algorithm, and students with the same grade stay alphabetically ordered. Merge, Insertion and Bubble Sort are stable; Selection, Quick and Heap Sort are not (as normally implemented).

Why isn’t Quick Sort always the fastest if it is O(n log n) on average?

Because its worst case is O(n²): with unlucky pivots, each partition peels off only one item. Good implementations avoid this with median-of-three pivot choice (as in this simulator) or randomisation. Merge Sort guarantees O(n log n) but needs O(n) extra memory; Heap Sort guarantees O(n log n) in place but jumps around memory, which modern caches dislike.

Does the simulator really run the algorithms, or is it an animation?

It really runs them. Each algorithm executes its genuine logic and emits step events — compare, swap, overwrite, pivot, merge, heapify — which the animated chart plays back. In Race mode all six run the same input side by side, so the comparison is fair. Words mode sorts text with accent- and case-insensitive comparison.

What is Big-O notation actually counting?

How the number of basic steps grows as the input grows, ignoring constant factors. O(n²) means doubling the input roughly quadruples the work; O(n log n) means doubling little more than doubles it. At n = 1,000,000 that is the difference between roughly a trillion operations and twenty million — a fraction of a second versus minutes or even hours.

Sources and further reading

Cite this exhibit

Eurekarium. (2026). Sorting Lab. https://eurekarium.com/computing/sorting-lab/

Last updated: