Insertion Sort

Insertion sort is a comparison sort algorithm with worst case complexity of O(n^2).

Insertion can be compared with the way cards are sorted manually in hand.

We first pick a card in hand. The 2nd card is picked and compared with first, if it is smaller it is placed ahead of it. The 3rd card is picked and compared with remaining cards in hand to find its final position.

At a time all the cards in hand are sorted and a new card is picked and “inserted” in its final position.

for (int j = 1; j < arr.length; j++) { 
    int key = arr[j]; 
    int i = j-1; 
    while (i >= 0 && arr[i] > key) {
        arr[i+1] = arr[i];
        i--;
    }
    arr[i+1] = key;
}

Complexity:

Worst case is when input is reverse sorted

T(n) = Total work done in each iteration.
In first iteration there is only one comparison
In second iteration there are two comparisons
and so on and so forth.
T(n) = 1 + 2 + 3 + … n = n^2 (arithmetic series)

Best case is already sorted array where complexity is O(n)

Git:
algorithms/src/main/java/org/nmn/notes/algorithms/sorting/InsertionSort.java

Advertisements