Insertion Sort

Insertion Sort sorts an array of elements by moving the element in position \(P\) left until it finds its correct place.

Analysis

• It will result in \(\Theta(N^2)\) in average and \(O(N^2)\) in worst case.

Implementation

Note: The implementation below sorts the items in ascending order.

void InsertionSort(ElementType A[], int N) {
  int j;

  ElementType Tmp;
  for (int P = 1; P < N; P++) {
    Tmp = A[P];
    for (j = P; j > 0 && A[j-1] > Tmp; j--)
      A[j] = A[j-1];
    A[j] = Tmp;
  }
}