The Insertion Sort Algorithm

An insertion sort walks through every item in a list in turn, starting with the second item.

• If the number is greater than or equal to the number to the immediate left, then it does nothing.
• If the number is less than the number to the immediate left of it, then it is moved one space to the left.
• If it is still less than the number to the left, then it moves one space to the left again. This process is repeated until the number is not less than the number to the left, or else it is the first item in the list.
• We then consider the next item in the list

For example when sorting this list of numbers, we start at the 2nd number in the list which is number 4:

The number is less than the number to the immediate left (4 < 10), so we move the number 4 one space to the left:

The number 4 is now the first number in the list so we do not need to do anything else with this number. Now we move onto the next item in the list (the 3rd number), which is 99. The number is greater than the number to the immediate left and so we do nothing.

Now we move to the 4th and final number in the list which is 7.

7 is less than the number to the immediate left, which is 99, and so we move it one space to the left.

However, 7 is still less than the number to the immediate left (10) and so we do another swap:

The number 7 is now no longer less than the number to the left and so we stop. We have no more numbers in the list to consider and so the list is in sorted order.

An insertion sort is usually faster than a bubble sort, but is generally not the fastest form of sorting algorithm except sometimes on small lists. A merge sort can often be faster but can use more memory than an insertion sort.

An Implementation of an Insertion Sort in Python

def insertion_sort_algorithm(list_of_numbers):
	
	list_length = len(list_of_numbers)
	
	#Step through every number in the list to be sorted beginning at the 2nd number
	for i in range(1, list_length ):

		position_marker = i	
		current_number = list_of_numbers[i]
		
		#Check if the number we are at is less than the number to the immediate left
		while current_number < list_of_numbers[position_marker-1] and position_marker > 0:
			#If so switch the number to the left into the current position in the list
			list_of_numbers[ position_marker ] = list_of_numbers[position_marker-1]
			#Then temporarily move one space to the left and check again
			position_marker -= 1
			
		#The number to the left is now not greater than the current number, so insert the current number here
		list_of_numbers[ position_marker ] = current_number
		

if __name__ == "__main__":
	
	list_to_sort = [ 10, 4, 99, 7 ]
	
	insertion_sort_algorithm( list_to_sort )
	
	print(list_to_sort)