Sorting — Putting Things in Order

Play

How computers compare and rearrange data, step by step

Computer Science Algorithms beginner 6 min

This concept builds on Binary Numbers — How Computers Count. Consider exploring it first for the best experience.

Step 1 of 7

The Problem

Each bar on the canvas is one number in random order, and the tallest bar is the largest. Every algorithm below gets the bars into ascending order, but they spend very different numbers of comparisons doing it. Watch the "Comparisons" card count them, and the green bars mark positions that are finally in place.

Bubble Sort

Click 'Bubble' to run it. The two yellow bars are the neighbours being compared; if the left one is taller, they swap. Each pass carries the tallest unsorted bar to the right end, where it turns green. The "Pass" card counts passes. Bubble sort makes up to about n²/2 comparisons, stopping early only when a pass needs no swaps.

Selection Sort

Click 'Selection' to run it. The orange bar is the smallest value found so far in the unsorted part, and the yellow bar is the one being checked against it. At the end of each pass the orange bar swaps to the front and turns green. It always makes exactly n(n−1)/2 comparisons but very few swaps.

Insertion Sort

Click 'Insertion' to run it. The bars on the left stay sorted; each new bar slides left past every taller neighbour until it reaches its place, so you see the sorted run grow one bar at a time. The worst case is still about n²/2 comparisons, but nearly sorted input finishes in close to n.

Merge Sort

Click 'Merge' to run it. The blue shaded band marks the two sorted halves being merged: the smaller front bar of each half is written back first, so the band leaves sorted. Halving the array gives about log₂ n levels of merging, each costing about n comparisons, for roughly n log₂ n in total.

Quick Sort

Click 'Quick' to run it. The rightmost bar of the current range is the pivot; each yellow comparison checks one bar against it, and smaller bars swap toward the left end of the range. The pivot then drops into its final slot and turns green. With lucky pivots that is about n log₂ n comparisons, but already sorted input degrades to n².

Worked Example: n = 10⁶

When a run finishes, the chart compares all five algorithms on the same array. Drag the 'Array size' slider to 30: 'Selection' makes 435 comparisons (30 × 29 ÷ 2) while 'Merge' makes roughly 110. Scale to n = 10⁶: n² = 10¹², but n log₂ n ≈ 10⁶ × 20 = 2 × 10⁷, so the ratio is about 50 000× fewer comparisons.

Play Crate Scales A game about Sorting — Putting Things in Order

How It Works — Step by Step

Step 1 of 7
  1. 1

    The Problem

    Each bar on the canvas is one number in random order, and the tallest bar is the largest. Every algorithm below gets the bars into ascending order, but they spend very different numbers of comparisons doing it. Watch the "Comparisons" card count them, and the green bars mark positions that are finally in place.

  2. 2

    Bubble Sort

    Click 'Bubble' to run it. The two yellow bars are the neighbours being compared; if the left one is taller, they swap. Each pass carries the tallest unsorted bar to the right end, where it turns green. The "Pass" card counts passes. Bubble sort makes up to about n²/2 comparisons, stopping early only when a pass needs no swaps.

  3. 3

    Selection Sort

    Click 'Selection' to run it. The orange bar is the smallest value found so far in the unsorted part, and the yellow bar is the one being checked against it. At the end of each pass the orange bar swaps to the front and turns green. It always makes exactly n(n−1)/2 comparisons but very few swaps.

  4. 4

    Insertion Sort

    Click 'Insertion' to run it. The bars on the left stay sorted; each new bar slides left past every taller neighbour until it reaches its place, so you see the sorted run grow one bar at a time. The worst case is still about n²/2 comparisons, but nearly sorted input finishes in close to n.

  5. 5

    Merge Sort

    Click 'Merge' to run it. The blue shaded band marks the two sorted halves being merged: the smaller front bar of each half is written back first, so the band leaves sorted. Halving the array gives about log₂ n levels of merging, each costing about n comparisons, for roughly n log₂ n in total.

  6. 6

    Quick Sort

    Click 'Quick' to run it. The rightmost bar of the current range is the pivot; each yellow comparison checks one bar against it, and smaller bars swap toward the left end of the range. The pivot then drops into its final slot and turns green. With lucky pivots that is about n log₂ n comparisons, but already sorted input degrades to n².

  7. 7

    Worked Example: n = 10⁶

    When a run finishes, the chart compares all five algorithms on the same array. Drag the 'Array size' slider to 30: 'Selection' makes 435 comparisons (30 × 29 ÷ 2) while 'Merge' makes roughly 110. Scale to n = 10⁶: n² = 10¹², but n log₂ n ≈ 10⁶ × 20 = 2 × 10⁷, so the ratio is about 50 000× fewer comparisons.

Key Takeaways

O(n²) vs O(n log n)

Bubble, selection, and insertion sort need roughly n² comparisons. Merge sort and quicksort need only about n log n — a dramatic improvement for large datasets. Change the array size and compare the chart after each run to see the gap grow.

In-Place vs Extra Memory

Bubble, selection, insertion sort, and quicksort rearrange the original array in place. Merge sort needs extra space proportional to n to hold the merged result.

Stability

A stable sort preserves the original order of equal elements. Merge sort, bubble sort, and insertion sort are stable; selection sort and quicksort (as commonly implemented) are not. Stability matters when sorting records by multiple keys.

Added
Updated
  • — Added a predict question on selection sort at 14 vs 28 bars, and a goal: sort 28 bars with a faster algorithm.
  • — Steps now follow the algorithm you pick, with a worked comparison-count example
  • — Corrected the speed-up figure (about 50,000×, not 400×) and synced step highlights with the running algorithm