Explain like I'm five · Systems

What is a Sort Algorithm?

Sort algorithms, told as a story about lining up customers' cars by size at the repair garage.

please line the cars up by sizethey're all mixed up — where do I even start?

The cars need to be lined up by size.They're all mixed up — where do you even start?

swap just these two?swapping at random just re-mixes the linewithout a fixed rule, there's no telling when you're done

Swapping at random never ends.Without a fixed rule, there's no telling when you're done.

a sort algorithm fixes a rule for comparing and swappingfollow the rule, and small-to-large order happens on its own

A sort algorithm fixes a rule for comparing and swapping.Follow the rule, and the order falls into place on its own.

Bubble sortcompare neighbors, push the bigger one back
Selection sortfind the smallest, put it in front
Insertion sortslide the new car into its spot
Merge/quick sortsplit in two, sort each part
speed as the line growsbubble/selection/insertion — one by one (slow)time: roughly n²merge/quick — split in two, sort each part (fast)time: roughly n log nthe speed gap widens as more cars line upwith many cars, splitting the problem in two is usually faster

The speed gap widens as the line of cars grows.With many cars, splitting the problem in two is usually faster.

with two or three cars, plain comparing beats splittingsplitting pays off once the line gets longthere's no single fastest sort — pick one for the situation

With few cars, the simple method is actually faster than splitting.There's no single fastest sort — you pick one for the situation.

In one breath

A sort algorithm is one of several rules for comparing and swapping items to line them up in order by size.

A sort algorithm rearranges data into a given order. Bubble, selection, and insertion sort are simple but make roughly n² comparisons for n items. Merge and quick sort use 'divide and conquer', splitting the problem into smaller parts, needing only about n log n comparisons (on average, for quick sort). Simple sorts win for small data; divide-and-conquer sorts win for large data.

When grown-ups say it

Bubble Sort
Compare neighbors, push the bigger one back. Simplest to implement, but slow with many cars.
Selection Sort
Find the smallest and put it in front. Makes about the same number of comparisons whatever the starting order.
Insertion Sort
Slide a new car into its correct spot in the line. Very fast on data that's already nearly sorted.
Merge Sort
Split the line in half, sort each half, then merge. Always about n log n, whatever the starting order.
Quick Sort
Pick a pivot car and split into smaller/bigger sides. Fast on average, slow if the pivots are picked badly.
Time Complexity
How fast time grows as the line grows. The gap between n² and n log n is the key idea.
Stable Sort
Keeping same-size cars in their original order. Merge sort and insertion sort are stable sorts.
Divide and Conquer
The strategy of splitting a problem, solving the parts, then combining. Merge sort and quick sort both use this strategy.
Next story
The Parts Warehouse That Remembers Even Off Power →
Want another term as a picture book? Request →