Where it runs
1. The problem
You have a list of numbers in no particular order, and you want them from smallest to largest. You did this with selection sort and bubble sort. This lesson uses a third method.
Take a leaderboard where scores arrive one at a time. The board already shows 2, 5 and 8, in order. A 3 arrives. You don't need to sort the whole board again: it is enough to insert 3 between 2 and 5. The board is in order again and one number longer.
That is how this method works. It takes the numbers one at a time and inserts each one into its place among the numbers already in order.
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 includedRecognise 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
Problems where values arrive one at a time and the list must stay sorted, or a sorted list has to take in new values. Shift the bigger values right and drop the new one into the gap.
Keep the scores sorted by inserting each new one into place, then read the kth largest.
nums1 has room at the end, so insert each value of nums2 by shifting the bigger values right.
Insertion sort in place passes on 300 values and keeps equal colors in their order.