Insertion Sort

• Premise
  • Keeps track of sorted and unsorted regions
  • One by one, insert elements in the proper place in the sorted region from the unsorted region
• Like if you were drawing cards one by one and sorting them in your hand
• Note: the first pass moves the first element into the first position, so nothing changes
• Comparisons is $O(n^2)$, Exchanges is $O(n^2)$

Implementation

for each array element from the second (nextPos = 1) to the last
	nextPos is the position of the element to insert  
	Save the value of the element to insert in nextVal  
	while nextPos > 0 and the element at nextPos – 1 > nextVal
		Shift the element at nextPos – 1 to position nextPos
		Decrement nextPos by 1
	Insert nextVal at nextPos

void insertionSort(int array[], int size) {
	for (int i = 1; i < size; i++) {
		int key = array[i];
		int j = i-1;
    
		// Compare key with each element in sorted
		// untill smaller value is found
		while (key < array[j] && j >= 0) {
			array[j+1] = array[j];
			j--;
	    }
		array[j+1] = key;
	}
}