Insertion Sort

This page provides introduction to Insertion Sort.

Overview

Insertion Sort builds the final sorted array one element at a time. It picks each element from the unsorted portion and places it in its correct position in the sorted portion by shifting larger elements to the right.

Let's sort array below, with insertion sort:

$$[12, 11, 13, 5, 6]$$

Step 1

Pick an element from unsorted portion of an array.

Place it in correct position in sorted array.

Step 2

Pick an element from unsorted portion of an array.

Place it in correct position in sorted array.

Step 3

Pick an element from unsorted portion of an array.

Place it in correct position in sorted array.

Step 4

Pick an element from unsorted portion of an array.

Place it in correct position in sorted array.

Java

public void insertionSort(int[] arr) {
  for(int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;
    while(j >= 0 && key < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

We are inserting an element from unsorted array into sorted array which takes $\text{O}(\text{N})$, so total time complexity will be:

$$\text{O}(\text{N}^2)$$

Space Complexity

Algorithm uses constant space.

$$\text{O}(1)$$

Leetcode Problem Set