Elementary Sorting Algorithms – Insertion Sort

Sorts while moving a pointer i from left to right, elements on the right are sorted by comparing the element at the pointer index with elements to its left and exchange their position if the element to the left is larger. Elements to the left of the pointer have not been visited yet.

The Invariants

  1. Elements to the right are sorted
  2. Elements to the left are not visited

Sample Code

for(int i = 0; i < a.length; i++){
    for(int j = i; j > 0; j--){
        if (less(a[j],a[j-1])){
            exchange(a[j],a[j-1]);
        }else{
            break;
        }
    }
}

Mathematical Analysis

  1. Proposition: To sort randomly-ordered array with distinct keys; the insertion sort uses (1/4)N^2 compares and (1/4)N^2 exchanges
0