Insertion Sort

Copy Link LinkedIn Message Facebook Email X

If you've ever played card games like Bridge, Hearts, or Poker, you'll be familiar with the Insertion Sort. The act of sorting your cards into a usable order for the game is essentially an insertion sort at work. Like the Bubble Sort, it is not well suited to large data sets with a Big O complexity of $`O(n^2)`$. However, it is more efficient than Bubble Sort if the data is already mostly sorted. It can also be used to sort items as they are received and added to the list, making it good for processing online data.

Insertion Sort Animation

Here's what these actions look like with a small dataset:

Credit: Swfung8, CC BY-SA 3.0, via Wikimedia Commons

Insertion Sort Big O Complexity

The big O complexity of insertion sort is $`O(n^2)`$, where n is the number of elements in the array. This is because insertion sort involves nested loops; for each element in the array, it may need to compare and shift elements multiple times. This requires nested loops, and the complexity therefore grows exponentially.

Insertion Sort Algorithm in Java

Enough already -- here's the code:

public static int[] insertionSort(int nums[]) {
  // iterate over the length of the array, skipping the first item
  for (int i = 1; i < nums.length; ++i) {
    // get the value at nums[i]
    // this is the next value to sort
    int val = nums[i];

    // get the index of the item before val
    int j = i - 1;

    // while j is 0 or greater, and nums[j] is greater than val
    while (j >= 0 && nums[j] > val) {
      // move the value of nums[j] to the right by one index
      nums[j + 1] = nums[j];
      // decrement j
      j--;
    }
    // once nums[j] is no longer bigger than val, you can insert it just
    // after nums[j]
    nums[j + 1] = val;
  }

  return nums;
}

Notice that you don't have two nested for loops but a while loop inside a for loop. This should suggest that this algorithm will be faster than the Bubble Sort, as the while loop will stop sooner than a for loop.

Here, the outer loop starts at the second item in the array rather than the first because you move smaller items to the beginning of the list. You pick the current item and store it in val -- this is the value you will sort on this iteration of the loop. You then find the index of the item just before val, store it in j, and start your while loop.

The while loop checks two conditions:

1. Is j still a valid index in the array?
2. Is the value at nums[j] greater than val?

If both of these are true, then you copy the value at nums[j] to nums[j+1], essentially moving the larger values toward the end of the list. When you have either run off the start of the list (when j<0) or found a value in the list that is less than or equal to val, you have found the place to insert val into the list, so you copy it to nums[j+1].

Notice there is no swapping going on -- since you are copying values each iteration of the inner while loop, there is no need to swap anything. This also means this algorithm can sort an array in place without needing any additional memory space. This is what makes this algorithm so efficient despite the $`O(n^2)`$ complexity.

Insertion Sort Algorithm in Python

This Python example below defines the function insertion_sort that takes in a list of nums as a parameter and sorts the nums list using the insertion sort algorithm. The insertion sort iterates through the list and compares each element with its adjacent elements. It then shifts elements to their correct positions, if needed, to build the sorted array.

def insertion_sort(nums):
  """
  This function performs the insertion sort algorithm on a list.
  :param nums: A list of comparable elements
  :return: The sorted list in ascending order
  """
  # Iterate through nums
  for i in range(1, len(nums)):
    key = nums[i]

    # Move elements of nums[0..i-1] that are greater than 
    # key to one position ahead of their current position
    j = i - 1
    while j >= 0 and key < nums[j]:
      nums[j + 1] = nums[j]
      j -= 1

    # Place the key at its correct position in the sorted subarray
    nums[j + 1] = key

return nums

# Example usage:
unsorted_list = [87, 34, 566, 12, 900, 45, 862, 345]
sorted_list = insertion_sort(unsorted_list)
print("Sorted array:", sorted_list)

Summary: Insertion Sort

So far, you've seen algorithms that are great for small data sets due to their complexity -- for larger data sets, you need to radically change your approach to sorting. As you've seen the big O complexity of insertion sort is $O(n^2)$. Not great.

The insertion sort mimics sorting a hand of cards in a card game, systematically inspecting and moving each item closer to its final position as you see it. While it's good for sorting data as it is being read, it is still a nested loop algorithm, which means it's complexity grows exponentially and it will suffer when processing large datasets.