## insertion sort:

**algorithm**: given an int array arr with length=n, define key=arr[i: i= 1~n-1], and need to put each key in the correct position, how? first save the key=arr[i], and compare the key with arr[j: j=0~i-1], if arr[j] is larger then move arr[j] to arr[j+1].

**how it works**: each time we define a key, we’ll need to compare the key with all its preceding elements, and the key’s preceding subarray is always in a increasing order.

**code**:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
/*Function to sort array using insertion sort*/ void sort(int arr[]) { int n = arr.length; for (int i=1; i<n; ++i) { int key = arr[i]; int j = i-1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j>=0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } |