Insertion Sort

If the first few objects are already sorted, an unsorted object can be inserted in the sorted set in proper place. This is called insertion sort. An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted).

Insertion sort is an example of an incremental algorithm; it builds the sorted sequence one number at a time.

INSERTION_SORT (A)

For j = 2 to length [A] do

    key = A[j]

    {Put A[j] into the sorted sequence A[1 . . j-1]

    i ← j -1

    while i > 0 and A[i] > key do

        A[i+1] = A[i]

            i = i-1

    A[i+1] = key

Analysis

Best-Case

The while-loop in line 5 executed only once for each j. This happens if given array A is already sorted.

T(n) = an + b = O(n)

It is a linear function of n.

Worst-Case

The worst-case occurs, when line 5 executed j times for each j. This can happens if array A starts out in reverse order

T(n) = an² + bc + c = O(n²)

It is a quadratic function of n.

The graph shows the n² complexity of the insertion sort.

Stability

Since multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array, Insertion sort is stable.

Extra Memory

This algorithm does not require extra memory.

For Insertion sort we say the worst-case running time is θ(n²), and the best-case running time is θ(n).
Insertion sort use no extra memory it sort in place.
The time of Insertion sort is depends on the original order of a input. It takes a time in Ω(n²) in the worst-case, despite the fact that a time in order of n is sufficient to solve large instances in which the items are already sorted.

Implementation

void insertionSort(int numbers[], int array_size)
{
  int i, j, index;

  for (i=1; i < array_size; i++)
  {
    index = numbers[i];
    j = i;
    while ((j > 0) && (numbers[j-1] > index))
    {
      numbers[j] = numbers[j-1];
      j = j - 1;
    }
    numbers[j] = index;
  }
}