Dima,s Blog: Insertion Sort - Algorithm (Simple sorting Techniques)

Hi, I described two simple sorting techniques in previous two posts. This post will describe Insertion sort.
Look at the following Unsorted array.

figure 01

Takeout an element from the array. Compare it with the elements with lower indexes. Shift those elements to right while find a smaller element than element 1. If n'th element is smaller than the selected element , insert element 1 in n+1'th place.

Round 01:

Step 01: Takeout element 1 from the array(figure 02).

figure 02

Step 02: Compare element 1 with element 0. element 0 is larger than element 1. So shift element 0 to position 1(figure 03).

figure 03

Step 03: Insert element 1 in position 0(figure 04).

figure 04

Round 02:

Step 01: Takeout element 2 from the array(figure 05). Assign it to a temp variable.

figure 05

Step 02: Compare temp with element 1. element 1 is larger than temp. So shift element 1 to position 2 (figure 06)

figure 06

Step 03: Compare temp with element 0. element 0 is smaller than temp. So insert temp in position 1 (figure 07).

figure 07

Round 03:

Step 01: Takeout element 3 from the array(figure 08) and assign it to temp.

figure 08

Step 02: compare temp with element 2. element 2 is larger than temp. So no need to shift. temp inserted in the position 3(figure 07).

Round 04:

Step 01: Takeout element 4 from the array(figure 09) and assign it to temp.

figure 09

Step 02: Compare temp with element 3. element 3 is larger than temp. So shift element 3 to position 4 (figure 10).

figure 10

Step 03: Compare temp with element 2. element 2 is larger than temp. So shift element 2 to position 3 (figure 11).

figure 11

Step 04: Compare temp with element 1. element 1 is larger than temp. So shift element 1 to position 2 (figure 12).

figure 12

Step 05: Compare temp with element 0. element 0 is smaller than temp. So no need to shift. Insert temp in position 1(figure 13)

figure 13

Overview

After four Rounds, the array is sorted.This technique can used when a part of the array is already sorted. This technique is better for almost sorted arrays.

figure 14: a partially sorted array

We don't need to worry about the sorted area. We can start the sorting from the beginning of the unsorted area. According to figure 14, sorting should start with element 5.

Java code for Insertion Sort