Insertion Sort

Internal

• Data Structures and Algorithms
• Sorting Algorithms

Overview

Insertion sort receives an array of integers and sorts the values in-place. It works as follows: we start from the left side of the array, and for each key, we insert it in the correct position in the already sorted sub-array that grows from left to right. The insertion is performed by scanning the sub-array from right to left in a while loop and swapping the elements until we reach the correct position of the key being handled.

public static void insertionSort(int[] a) {

  // handle trivial cases when the array is empty or has just one element

  // going forward, we assume the array has at least two elements

  for(int i = 1; i < a.length; i ++) {

    // if larger or equal, the key is in the right position, advance ...
    if (a[i] >= a[i - 1]) {
      continue;
    }

    // the key is smaller than the last one in the sorted subarray, 
    // send it through the subarray until it reaches the correct position

   

  }
}