An Insertion Sort

InsertionSort.cpp

void insertionSort(Array * S, int n) {
  if (n <= 1) return; // 1. Base case: Return if last (null) mem point
  insertionSort(S, n-1); // 2. recursively go through each element in array, starting with last
  int last = S[n-1];  // 3. set current last element
  int j = n-2; // 4. Run through each previous element
  while (j >= 0 && S[j] > last) { // 5. While that element is bigger than the last element
    S[j+1] = S[j]; // 6. Move its location forward in the array.
    j--; // 7. Go on to the next element in array.
  }
  S[j+1] = last; // 8. set last element to the final point in the array.
}