O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required