Insertion Sort Algorithm

3 min readSep 17, 2022

--

A in-place sorting algorithm that virtually splits an array into a sorted subarray and an unsorted subarray. Then it takes an element from the unsorted subarray and insert it into the correct position in the sorted subarray. The average and worst time complexity of insertion sort is O(n²), so it is not suitable for large data sets.

Table of Contents· How Does Insertion Sort Algorithm Work?
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How Does Insertion Sort Algorithm Work?

Image you are playing cards, the cards in your hands are sorted in order. When you receive a new card, you insert it into the current place in your sorted cards. Similarly, insertion sort virtually divided an array into two parts, one is sorted and another is unsorted. The sorted part is just like the sorted cards that are already in order. The algorithm inserts the item from the unsorted part into the sorted collections one by one until the array is completely sorted.

Graphical Explanation

step1: Image the array is split into a sorted subarray and an unsorted subarray initially. Because the first item(at index 0) in the array is already in the sorted subarray, we pick an item from the unsorted subarray to insert starting with index 1.

step2: Compare the item we took from the unsorted subarray to all the items in the sorted subarray from the last one.
If the set of the comparison items are out of order, we swap them. Otherwise, we can stop the comparison because we have inserted the picked item at a current place in the sorted subarray.
step3: Repeat step1 and step2 until the array is completely sorted.

Code Implementation

Complexity

Time: Best O(n), Average O(n²), Worst O(n²)
Space: O(1)
n: the total number of elements in the input array

Pseudocode

# the first item (index 0) is already in the sorted subarray
# pick the unsorted elements from index 1
for i from 1 to len(array):
    j := i
    # compare the item we try to insert to all elements in sorted subarray
    while j > 0 and array[j-1] > array[j]:
        swap array[j-1] and array[j]
        j -= 1

Golang

Python

You can access the source code here.

Other sorting algorithms: