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.
/*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;