How to Implement Insertion Sort In C

We start with a function called sort, which takes as input an array, T, and its length, n.

void sort(int T[], int n)
{
  // ...
}

We loop, with the index i remembering the size of the green segment.

void sort(int T[], int n)
{
  for (int i = 1; i < n; ++i) {
    // ...
  }
}

We store the element to be inserted, which is positioned just after the green segment, in a temporary location.

void sort(int T[], int n)
{
  for (int i = 1; i < n; ++i) {
    int temp = T[i];
    // ...
  }
}

We loop over all elements in the green segment larger than the element to insert.

void sort(int T[], int n)
{
  for (int i = 1; i < n; ++i) {
    int temp = T[i];
    int j;
    for (j = i; j > 0 && T[j - 1] > temp; --j) {
      // ...
    }
  }
}

We shift these elements by one position towards the right.

void sort(int T[], int n)
{
  for (int i = 1; i < n; ++i) {
    int temp = T[i];
    int j;
    for (j = i; j > 0 && T[j - 1] > temp; --j) {
      T[j] = T[j - 1];
    }
  }
}

We place the current element in the position freed by the last shifted element.

void sort(int T[], int n)
{
  for (int i = 1; i < n; ++i) {
    int temp = T[i];
    int j;
    for (j = i; j > 0 && T[j - 1] > temp; --j) {
      T[j] = T[j - 1];
    }
    T[j] = temp;
  }
}

Page 1 – Introduction and Overview

Page 2 – How to Implement Insertion Sort in C

Page 3 – Time Complexity