Algorithm

Every iteration of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.

Sorting is typically done in-place. The resulting array after k iterations has the property where the first k + 1 entries are sorted. In each iteration the first remaining entry of the input is removed, inserted into the result at the correct position, thus extending the result:

becomes

with each element greater than x copied to the right as it is compared against x.

The most common variant of insertion sort, which operates on arrays, can be described as follows:

1. Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array. It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effect of overwriting the value stored immediately after the sorted sequence in the array.
2. To perform an insertion sort, begin at the left-most element of the array and invoke Insert to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined. Each insertion overwrites a single value: the value being inserted.

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        done := false;
        repeat
            if A[j] > value then
            begin
                    A[j + 1] := A[j];
                    j := j - 1;
              if j < 0 then
                        done := true;
            end
            else
                     done := true;
        until done;
         A[j + 1] := value;
    end;
end;

def insertion_sort(array):
    for i in xrange(1, len(array) - 1):
        temp_value = array[i]
        j = i - 1
        while j > 0 and array[j] > temp_value:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = temp_value
    return array


by C++ :

int * insertionsort(int *A; int length)
{
	for (int i = 0; i <= length-2; i++)
	{
		int value = A[i];
		int j = i - 1;
		bool done = false;
		do
			if (A[j] > value)
			{
				A[j + 1] = A[j];
				j -= 1;
				if (j < 0)
					done = true;
			}else
				done = true;
		while !done;
		A[j + 1] = value;
	}
        return A;
}