Take the first element of the array, consider it as sorted.

Then take the second element compare it with the previous if the first element is greater than the second then move the first element one cell backward and insert the second element in the first cell. Then we have a sorted array of two elements.

Then consider the third element and compare it with values of the previous cells move any element with value greater than the current element one cell forward and inset the current value in the correct place, this step results an array of three elements that are in the correct order.

Repeat these steps for all the elements in the array.

__Insertion Sort Algorithm, C++ implementation__

void InsersionSort(int* A, int length) { int temp = 0; for (int i = 0; i < length; i++) { for (int j = i; j > 0; j--) { if (A[j - 1] > A[j]) { temp = A[j - 1]; A[j - 1] = A[j]; A[j] = temp; } } } }