insertion sort

Summary

Insertion sort

• comparison based
• iterative
• in-place
• stable

Time complexity

• best case: - array already sorted, inner loop runs in
• worse case: - array is sorted in reverse, inner loop runs in
• every iteration of the outer loop sorts 1 element

Loop invariant

• at the kth pass, the first k elements are in order, but not necessarily at their final positions

Concept

Algorithm

1. start with a “sorted” array of the first element
2. pick the next element
3. insert it into the sorted part in the proper order(compare)
4. repeat 2-3 for the rest of the elements

for (i = 1; i <= N; ++i) { // N-1 times
  e = A[i]; j = i;  
  while (j > 0) {  
    if (A[j-1] > e)  
      A[j] = A[j-1];  
    else  
      break;  
    j--;  
  }  
  A[j] = e;  
}

build a sorted array, “insert” each new element into the sorted part