An Introduction to the Insertion Sort Algorithm

Insertion Sort is a technique that works by utilizing a sorted sublist and continuously adding a value to it from the unsorted list until the whole list is sorted.

The algorithm begins with the first list item as the sorted sublist. It then compares the next number with the first. If it’s greater, then it’s inserted in the first index. Otherwise, it’s left in its index.

The third value is then compared with the other two, and then inserted into the correct index. This process goes on until the whole list is sorted.

A Closer Look at Insertion Sort

The description above may not have made sense to you. An example should help you understand much better.

Suppose you have a list: [39, 6, 2, 51, 30, 42, 7].

The algorithm identifies 39 as the first value of the sorted sublist. Evaluation then moves on to the second position.

Related: Dynamic Programming: Examples, Common Problems, and Solutions

6 is then compared with 39. Since 6 is less than 39, 6 is inserted in the first position and 39 in the second. The new list order is after the first pass is now:

[6, 39, 2, 51, 30, 42, 7]

Evaluation now shifts to the third position. 2 is compared with the last two numbers and then inserted in the right position. The new list order is after the second pass is now:

[2, 6, 39, 51, 30, 42, 7]

For the third pass, the list order is:

[2, 6, 39, 51, 30, 42, 7]

The process repeats until the entire list is sorted.

See the diagram below that summarizes these operations:

Algorithm analysis

The time complexity of Insertion Sort is O(n²), just like bubble sort. The number of comparisons in the worst-case scenario is the sum of all integers from 1 to (n-1), giving a quadratic sum.

Code Implementation

The Python and Java code below shows how you can implement the Insertion Sort method.

Python:

def insertionSort(mylist):
  for step in range(1, len(mylist)):
     current_element = mylist[step]
     position = step
     while position > 0 and mylist[position - 1] > current_element:
         mylist[position] = mylist[position - 1]
         position = position - 1
   mylist[position] = current_element

Java:

void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x < n; x++) {
int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
}

Better Coding With Pseudocode

The code examples above were given without any pseudocode that you can reference to write this algorithm in other languages. Most programmers (the author included) like to run to their keyboards after being told “whispers” about how a program works.

This approach is unfortunately prone to errors as the program logic gets more complicated. How would you like to level up your programming game by learning how to use pseudocode?

MUO – Feed