Where it runs
1. The problem
You have a list of numbers in no particular order, and you want them from smallest to largest. A game lobby shows five players with scores 40, 15, 27, 8 and 31. You want the leaderboard in order, from the lowest score to the highest.
So far you searched a list for one value. Now you have to put the whole list in order. The simplest way to sort is to ask one question again and again: which number is the smallest among the ones not yet in their place?
Keep answering that question, and the list ends up sorted.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedinsertionSort([5, 2, 4, 6, 1, 3])Sort [5, 2, 4, 6, 1, 3] with insertion sort. The part on the left is sorted; at the start it is just 5.
One operation is one comparison or one move. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n²)O(n²)O(n log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- n is small (tens or a few hundred)
- array is nearly sorted already
- sort in place with O(1) extra space
- teaching/interview question about how sorting works
- stability matters and simplicity is fine
Looks similar, isn't
- Fast sort (merge / quick)
Merge and quick sort split the array and cost n log n. These three never split anything.
- Non-comparison sort (counting / radix)
Counting sort reads the values instead of comparing them. That needs a small range of keys.
- Sort with a custom comparator
That page is about which order you want. This one is about how the order is produced.
- Binary heap / priority queue
Selection sort scans for the smallest value every round. A heap hands it over in log n.
n up to roughly 5000 is fine at O(n squared). Insertion sort drops to O(n) on nearly sorted data.
On LeetCode
Selection sort is too slow for LeetCode's large sorting tests, so these problems keep n small, at most a few thousand. They ask you to order a short list or compare a list with its sorted copy.
Sort a copy with selection sort, then count the places where it differs from the original.
Pick the tallest remaining person on each pass and swap the name along with the height.
Only 300 values, so selection sort in place passes, even though one pass is possible.