Sorting Algorithms - Insertion Sort

Pic from Geeksquiz

Insertion Sort is utilized to sort a group of elements from smallest to largest. Here's how it works:

Lets say we start with an array A = {15, 16, 12, 7, 9}. This array is not sorted(least to greatest).

Pseudocode:

Insertion-Sort(A)

1.    for j = 2 to A.length do

2.        key = A[j]

3.        i = j - 1

4.        while i > 0 and A[i] > key do

5.            A[i+1] = A[i]

6.            i = i - 1

7.        A[i + 1] = key

Walk-through:

Starting with the unsorted array {15, 16, 12, 7, 9}...

line #1: j is 2. array is unchanged {15, 16, 12, 7, 9}

line #2: key is 16

line #3: i is 1

line#4: loops while i is not going out of bounds and A[i] is bigger than the key(current j that we are comparing)

line#7: we skipped lines 5 and 6 because A[i](15) was not bigger than key(16). We basically copy the key back into i + 1 in which this case it is also j.

line#1: j = 3 array is {15, 16, 12, 7, 9}

line#2: key is 12

line#3: i is 2

line#4: loops while i is not going out of bounds and A[i] is bigger than the key(current j that we are   comparing)

line#5: 16 > 12, so A[i + 1] = A[i] OR {15, 16, 16, 7, 9}

line#6: i is 1

line#7: A[i + 1] = key OR {15, 12, 16, 7, 9}

line#5: 15 > 12, so A[i + 1] = A[i] OR  {15, 15, 16, 7, 9}

line#6: i is 0

line#7: A[i+1]  = key OR {12, 15, 16, 7, 9}

See here that first three elements are now already sorted, if we keep going with the pseudocode we will eventually come to the sorted {7, 9, 12, 15, 16}. Try doing the rest!

Analysis: 

Worst Case: The worse array that can go through this is some array that is sorted in reverse order e.g, {19, 15, 13, 7, 3, 1} 

In this case, the algorithm will have to go through and compare each number to more and more numbers.

For example, the worst case array presented here will first compare 15 once, then compare 13 twice, then 7 three times, 3 four times, and 1 five times:

                                                     1 + 2 + 3 + 4 + 5........

In terms of the length of the array n, it will compare a total of:
                                                            n(n + 1)/ 2  OR  (n^2 + n)/2 times

As you accumulate more knowledge or already have, you will see that O(n^2) is not very nice a time compared to some others.