The problem
Write insertion sort. Sort the list a in place: change the list you were given, and return nothing.
a = [29, 10, 14, 37, 13, 5, 21]
insertion_sort(a)
a # [5, 10, 13, 14, 21, 29, 37]
One test is a list of 100,000 values that is nearly in order: no value is more than 3 places from where it belongs. Lesson 1 explains why insertion sort is fast there and selection sort is not. sorted() and .sort() are switched off.
Limits
- Up to 2,000 values in any order, or up to 100,000 values that are nearly in order.
Builds on SORT-1 Selection, insertion and bubble sort.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
7 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Mixed | Not run | |
| 2 | Reversed | Not run | |
| 3 | Already sorted | Not run | |
| 4 | Repeats | Not run | |
| 5 | Empty and one | Not run | |
| 6 | 2,000 values | Not run | |
| 7 | 100,000 values, nearly in order | Not run |