Insertion Sort
EasyInsert each key into a sorted prefix
Take one card at a time and slide it back into its right place among the cards you've already sorted.
The idea
Treat the left part as sorted. Take each new element and slide it left past everything larger until it drops into place. Excellent on nearly-sorted data.
5
2
4
6
1
3
0
1
2
3
4
5
Step 1 of 21. Grow a sorted prefix. Take each new key and slide it left past everything larger. Values: 5, 2, 4, 6, 1, 3.
1/21
Brute force
timeO(n²)spaceO(1)
O(n) on nearly-sorted input.
1// grow a sorted prefix, inserting each key into place2for (let i = 1; i < n; i++) {3 const key = a[i];4 let j = i - 1;5 while (j >= 0 && a[j] > key) {6 a[j + 1] = a[j];7 j--;8 }9 a[j + 1] = key;10}Input
- array
- [5, 2, 4, 6, 1, 3]
Memory
- key
- —
- j
- —
Output
- result
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [12, 11, 13, 5, 6]
- Output:
- [5, 6, 11, 12, 13]
- Explanation:
- Insert each card into its sorted place.
Example 2
- Input:
- nums = [4, 3, 2, 1]
- Output:
- [1, 2, 3, 4]
- Explanation:
- Each element slides left into position.
Example 3
- Input:
- nums = [2, 1]
- Output:
- [1, 2]
- Explanation:
- One insertion sorts a pair.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.