Blog PostAboutGithub

Insertion Sort

Purpose: Sort a list of comparable elements.
Runtime: O(N^2), where N is the number of list elements. Insertion sort is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, which run in O(N*log(N)).
Algorithm Steps:
  • For each element, moving from left to right:
    • Move the element into the sorted subarray. One way to do this is by swapping side-by-side elements repeatedly.
Slide 0 of 20
Slide 0
Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Use Arrow keys

Python Code

def insertion_sort(lst):
  for i, cur in enumerate(lst):
      j = i - 1
      while j >= 0 and lst[j] > cur:
          lst[j], lst[j + 1] = lst[j + 1], lst[j]  # alternatively, use temporary var
          j -= 1
      lst[j + 1] = cur


lst = [1, 8, 32, -3, 2, 10, 1, 5, 100]
insertion_sort(lst)
print("list sorted:", lst)