Insertion sort

• divides an array into a sorted and unsorted segment
• Steps
  • loop until unsorted segment reaches length 0
    • get first element in unsorted segment
      • iterate back through sorted segment and insert selected element into it’s ordered position
        • insertion involves shifting everything after the element ordered below along by 1 to make space for insertion
      • ^ sorted segment logically increases by 1 in length

Pseudo implementation

BEGIN InsertionSort()
array = array[]
index = 0
while index < len(array)
element = array[index]
subIndex = 0
while subindex < index:
if element < array[subindex+1]
bubbleindex = index-1
while bubbleindex > subindex:
array[bubbleindex] = array[bubbleindex -1]
bubbleindex = bubbleindex - 1
array[subindex] = element
subindex = subindex +1
index = index +1
END InsertionSort()