Insertion Sort

Insertion Sort#

Contents#

Problem#

 INPUT     an array A[1:n] of n values
OUTPUT    the array A in ascending sorted order

INSERTION_SORT(A, n)
1  for i = 2 to n
2     key = A[i]
3     j   = i - 1
4     while j > 0 and A[j] > key
5         A[j + 1] = A[j]
6         j        = j - 1
7     A[j + 1] = key

Description#

Insertion sort takes time roughly equal to \(c n^2 \propto n^2\) to sort \(n\) items where \(c\) is a constant that does not depend on \(n\).

Insertion sort uses an incremental algorithm design method: for each element \(A[i]\), insert it into its proper place in the subarray \(A[1:i]\) having already sorted the subarray \(A[1:i - 1]\)

Complexity#

Time#

The outer loop iterates from the second to the last element.

\(\Theta(n^2)\) Worst-Case#

INSERTION_SORT(A, n)
1  for i = 2 to n                //   n - 1
2     key = A[i]
3     j   = i - 1
4     while j > 0 and A[j] > key //   n(n + 1)/2 - 1
5         A[j + 1] = A[j]
6         j        = j - 1
7     A[j + 1] = key

\(\Theta(n)\) Best-Case#

INSERTION_SORT(A, n)
1  for i = 2 to n                //   n - 1
2     key = A[i]
3     j   = i - 1
4     while j > 0 and A[j] > key //   1
5         A[j + 1] = A[j]
6         j        = j - 1
7     A[j + 1] = key

Space#

Correctness#

\(\textbf{Invariant}\)

At the end of iteration \(i\) (NOT the \(i\)-th iteration), subarray \(A[1:i]\) contains the first \(i\) elements of the array \(A\) but in sorted order.

\(\textbf{Initialization}\)

\(i = 2\) and subarray \(A[1:1]\) contains the first element of the array, which is trivially in sorted order.

\(\textbf{Maintenance}\)

The body of the for loop works by moving the values \(A[i - 1], A[i - 2], A[i - 3],\) and so on by one position to the right until it finds the proper position for \(A[i]\) (lines 4-7), at which point it inserts the value of \(A[i]\) (line 8). The sub array \(A[1:i]\) then consists of the elements originally in \(A[1:i]\) but in sorted order. Incrementing \(i\) for the next iteration of the for loop then preserves the loop invariant.

\(\textbf{Termination}\)

The loop variable \(i\) starts at \(2\) and increases by \(1\) in each iteration. Once \(i\)’s value exceeds \(n\) in line 1, the loop terminates. That is, the loop terminates once \(i = n\). Substituting \(n\) for \(i\) in the wording of the loop invariant yields that the sub array \(A[1:n]\) consists of the elements originally in \(A[1:n]\) but in sorted order.

Implementations#

C#

/*   insertion_sort.c
 *
 */

#include <stdio.h>

void print_array (int A[], int n) {
  for (int i = 0; i < n; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");
}

void insertion_sort (int A[], int n) {
  int i, j, key;

  for (i = 1; i < n; i++) {        // C arrays are zero-indexed! second to last elem
    key = A[i];
    j   = i - 1;
                                   // iterate from right to left over the sorted subarray
    while (j >= 0 && A[j] > key) { // if this elem is larger than A[i]
      A[j + 1] = A[j];             // shift this elem to the right one position
      j        = j - 1;            // move left one position to the next elem
    }
    A[j + 1] = key;                // place A[i] into its proper position in the sorted subarray
  }
}

int main () {
  int A[] = {5, 4, 3, 2, 1};
  int n   = sizeof(A) / sizeof(A[0]);

  print_array(A, n);
  insertion_sort(A, n);
  print_array(A, n);

  return 0;
}

Python#

# insertion_sort.py

def insertion_sort (A, n):
  for i in range(1, n):
    key = A[i]
    j   = i - 1
    while j >= 0 and A[j] > key:
      A[j + 1] = A[j]
      j       -= 1
    A[j + 1] = key

A = [5, 4, 3, 2, 1]
n = len(A)

print(A)
insertion_sort(A, n)
print(A)

Acknowledgments#

Contents