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  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  & 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].
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 –
doSort()method in the above java program holds the sorting logic.
- There are 2 loops. The loop with the counter
outerrepresents the passes and continues for
length - 1times. i.e. 1 less than the number of items times.
- The loop with the counter
innerrepresents the progressive picking of the head element from the unsorted sub-list. Note that the loop for
inneriterates 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.
continuekeyword in the inner loop prevents unnecessary iterations for inner loop once the correct place for the item being inserted is found.
main()method orchestrates the sorting.
- The instance element
intArrayholds the list to be sorted.