Introduction to Insertion Sort

Insertion sort is a stable, in-place sorting algorithm that builds the final sorted array one item at a time. It is not the very best in terms of performance but more efficient traditionally than most other simple O(n2) algorithms such as selection sort or bubble sort. Insertion sort is can be used within the same array but is more clear if the sorted output is put in a separate "template" array instead.

How to perform: Insertion Sort

  1. Iterate through the list
  2. Take the second unsorted index and compare the data with the data at first index
  3. Swap if data at second index is smaller
  4. Take the next unsorted index and compare it with the data to the left of it
  5. Swap if compared data is larger than the data at unsorted index
  6. Repeat steps 4-5 until the entire list has been iterated over

Example of Insertion Sort

Example of Insertion Sort

Learn more about Insertion Sort