Algorithms
Insertion Sort
O(n²) time in the worst case · O(n) time if the list is already nearly sorted · O(1) space.
The idea, in plain English
Insertion sort is how most people sort a hand of playing cards. You pick up cards one at a time. You slide each new card into its correct spot among the cards you already hold.
How it works
- 1Start with the second item and compare it to the items on its left.
- 2Slide bigger items one spot to the right to make room.
- 3Drop the item into its correct place. Repeat for every item.
When you'd use it
Use it for small lists, or lists that are already almost sorted — it is genuinely fast there.
Common beginner mistakes
- Overwriting a value before you save it in a temporary variable.
- Running the inner loop past the start of the list.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
Expected output — hit Run to try it
Before: 5 2 9 1 5 6
Sorted: 1 2 5 5 6 9See it in motion
Watch it sortInsertion sortO(n²) time in the worst case · O(n) time if the list is already nearly sorted · O(1) space.
Ready. Press play to watch it sort.
0
Comparisons
0
Writes
0/26
Step
0.0s
Time
ComparingSwappingSorted
Not sure this is the right topic? See the learning paths → or where this leads →