What is Insertion Sort

Insertion sort works by progressively sorting a sub-list of the given list of items. With every iteration\pass the insertion sort algorithm keeps *inserting* the next item in the list in the correct position in this sorted sub-list.I.e. with every pass one item more is picked from the unsorted portion and is inserted in to the correct place in the sorted portion.

YouTube video showing whiteboard animation video explanation of how insertion sort works and Java code walk-through

Insertion Sort’s working explained

Lets say the list which is to be sorted is [1000, 1, 100, 101, 15]. Now we will progressively build a sorted sub-portion of the list from the left of the list. We will call this left sorted sub-portion as *sorted sub-list*. And the other unsorted portion on the right of the list as *unsorted sub-list*.

Before we start with the insertion sort passes – the first item, 1000, is assumed to be *sorted *by virtue of being the only element and is deemed to be sorted in a single item list. Sorted sub-list thus has [1000] at this point. The insertion sort passes start with picking of the second element.

First pass of Insertion Sort

Before the pass: Sorted sub-list is [1000] & Unsorted Sub-list is [1,100,101,15].

The item at the head of the unsorted sub-list, i.e. 1, is picked to be placed in the sorted sub-list. Since 1 < 1000 it is placed before 1000 in the sorted sub-list. To make space for 1 the item 1000 is moved to the right by 1 place.

At the end of the pass: Sorted Sub-List is [1,1000] & Unsorted Sub-list is [100,101,15].

Second pass

At the start of second pass: Sorted Sub-List is [1,1000] & Unsorted Sub-list is [100,101,15] *i.e same as the end of first pass*.

We pick item at the head of unsorted sub-list,i.e 100, and place it at the correct place in the sorted sub-list. Since, 100 > 1 and 100 < 1000 so 1000 is moved 1 place to the right and 100 is placed before 1000.

At the end of the pass: Sorted sub-list is [1,100,1000] & Unsorted Sub-list is [101,15].

Remaining passes of the algorithm

In this way progressively every element from the head of the unsorted sub-list is picked up and inserted in its correct place in the sorted sub-list in exactly n-1 passes.

Lets look at the code for Insertion Sort in Java –

package com.javabrahman.algorithms.sorts; public class InsertionSort { static int intArray[] = { 1000, 1, 100, 101, 15 }; public static void doSort() { for (int outer = 1; outer < intArray.length; outer++) { for(int inner=outer;inner > 0; inner--){ if(intArray[inner] < intArray[inner-1]){ int temp=intArray[inner]; intArray[inner]=intArray[inner-1]; intArray[inner-1]=temp; continue; }//if condition ends }//inner loop ends }//outer loop ends } public static void printArray() { for (int i = 0; i < intArray.length; i++) { System.out.print(" " + intArray[i]); } } public static void main(String args[]) { System.out.print("Array Before Sorting->"); printArray(); doSort(); System.out.print("\nArray After Sorting ->"); printArray(); } }

**OUTPUT of the above code**

Array After Sorting -> 1 15 100 101 1000

- The
`doSort()`

method in the above java program holds the sorting logic. - There are 2 loops. The loop with the counter
`outer`

represents the passes and continues for`0`

to`length - 1`

times. i.e. 1 less than the*number of items*times. - The loop with the counter
`inner`

represents the progressive picking of the head element from the unsorted sub-list. Note that the loop for`inner`

iterates in*reverse*. It starts its iterations with the unsorted item and keeps on moving the items greater than this unsorted item to the right by progressively swapping the items greater than itself.While doing all this the inner loop keeps decrementing its counter in order to iterate in reverse. - The
`continue`

keyword in the inner loop prevents unnecessary iterations for inner loop once the correct place for the item being inserted is found. - The
`main()`

method orchestrates the sorting. - The instance element
`intArray[]`

holds the list to be sorted.

Copyright © 2014-2016 JavaBrahman.com, all rights reserved.