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

void insertionSort(int[] A) {
	int N = A.length;

	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