Insertion Sort

Insertion Sort is a sorting algorithm that works by iteratively moving each element to the left until it reaches its sorted position. It is often introduced as the first sorting algorithm in education settings due to its simplicity and ease to understand.

The algorithm works by looping through the entire list, and for each element, we move it as far to the left as possible. The result of this is that as the algorithm processes, the elements will be placed in ascending order.

Time complexity analysis

There are two main scenarios to account for when analyzing Insertion Sort. The first scenario is when the input list is already sorted, and the second scenario is for any other list.

When the input list is sorted, the algorithm will not have to move any elements. In the inner loop, this means only a single iteration per element, because there is no need to move the element. In this scenario, the time complexity of Insertion Sort is .

For any scenario when the list is not already sorted, the algorithm will have to move the element up to times where denotes the original index of the current element. The absolute worst case is when the input list is sorted in reverse order, as each element will be moved the maximum number of times. In both cases described, the time complexity of Insertion Sort is .

Space complexity analysis

Because the algorithm only moves elements within an existing list, there are zero allocations required. The space complexity is thus .

Implementation

Java Implementation

package jun.codes.interviews.sort;

public class InsertionSort {
  public static <T extends Comparable<T>> void sort(T[] xs) {
    // For each element in the list, we move it as far left as possible
    for (int i = 0; i < xs.length; i++) {
      T elem = xs[i];
      // The variable j indicates the index of the element to our left. As the
      // algorithm moves, j becomes the left neighbor of the index elem is to be
      // placed at.
      int j = i - 1;

      // If there is an element to the left, and it's larger, then we shift the
      // element that is currently at j with its neighbor to its right.
      while (j >= 0 && xs[j].compareTo(elem) > 0) {
        xs[j + 1] = xs[j];
        // Since the element we just probed was larger than elem, we move left
        // one more position
        j--;
      }

      // The original spot of elem has been occupied by the items that we have
      // shifted. Now that j is the neighbor of the ideal spot for elem, we
      // set it.
      xs[j + 1] = elem;
    }
  }
}

Further reading

The relevant material in Introduction to Algorithms 4th edition can be found starting on page 17.

• Wikipedia: Insertion Sort