A Common-Sense Guide to Data Structures and Algorithms

Insertion Sort Implemented

Here is a Python implementation of Insertion Sort:

def insertion_sort(array):
   for index in range(1, len(array)):

     position = index
     temp_value = array[index]

     while position > 0 and array[position - 1] > temp_value:
         array[position] = array[position - 1]
         position = position - 1

     array[position] = temp_value

Let’s walk through this step by step. We’ll first present the line of code, followed by its explanation.

for index in range(1, len(array)):

First, we start a loop beginning at index 1 that runs through the entire array. The current index is kept in the variable index.

position = index
temp_value = array[index]

Next, we mark a position at whatever index currently is. We also assign ...