Easy Shift & Place Sorting
In plain English: Sort a list by repeatedly picking the next element and inserting it into its correct spot.
Builds the sorted portion one element at a time by shifting — efficient for nearly-sorted data because few shifts are needed.
Prompt
Sort an array using insertion sort.
Try to write it from scratch before scrolling down.
Solution
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key: # shift larger elements right
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
# Test: insertion_sort([5,3,1,4,2]) == [1,2,3,4,5]