Insertion Sort Explained

5 min readMay 6, 2023

Overview

Insertion Sort is a simple algorithm that sorts a list of unsorted elements by repeatedly inserting each element into its proper place in a partially sorted list. NOTE: Insertion Sort is best used on small datasets because of its simplicity and relatively low overhead. It has a time complexity of O(n²), meaning that its worst-case running time increases rapidly as the number of elements in the dataset grows. This makes insertion sort impractical for sorting very large datasets.

How do I recognize the pattern?

Insertion sort involves sorting an array by inserting each element into its proper position within a partially sorted array. The pattern for insertion sort involves iterating through the unsorted portion of the array and moving each element to its correct position within the sorted portion of the array.

Here are a few hints you can look for to determine if insertion sort is a good choice:

Small dataset: If the problem involves sorting a small dataset, insertion sort may be the best choice. Insertion sort is a simple algorithm that has a low overhead, making it efficient for small datasets.
Partially sorted data: If the dataset is partially sorted, insertion sort can be a good choice because it will only need to perform a small number of swaps to put the remaining elements in their correct positions.
In-place sorting: If the problem requires an in-place sorting algorithm, insertion sort is a good choice. Insertion sort is an in-place sorting algorithm, which means it does not require additional memory to sort the dataset.
Preserving the order of equal elements: If the problem requires that the order of equal elements in the dataset is preserved after sorting, insertion sort can be a good choice. Insertion sort is a stable sorting algorithm, which means it preserves the order of equal elements.

Overall, the best sorting algorithm to use depends on the specific problem requirements and the characteristics of the dataset.

Pseudocode

Here are the general steps for the pattern of insertion sort:

Start with an unsorted array of numbers.
Iterate through the unsorted portion of the array, starting from the second element.
For each element in the unsorted portion of the array, compare it to the elements before it in the sorted portion of the array.
If the current element is smaller than the previous element, swap them.
Continue to move the current element to the left within the sorted portion of the array until it is in its correct position.

Repeat steps 2–5 until all elements in the unsorted portion of the array have been moved to their correct positions.

The array is now sorted.

Let’s run through an example

Let’s review an easy problem.We have an unsorted array s and we are asked to return the sorted array.

Here’s an example of the pattern for insertion sort on the array s, where sis equal to [5, 2, 4, 6, 1, 3]:

First, we start with the unsorted array [5, 2, 4, 6, 1, 3].
We start iterating through the unsorted portion of the array from the second element 2.

Fig. Start with the Second (2nd) Element during iteration

We compare 2 to the first element 5in the sorted portion of the array and swap them to get [2, 5, 4, 6, 1, 3].
We continue to move 2 to the left within the sorted portion of the array until it is in its correct position, resulting in [2, 5, 4, 6, 1, 3].

Fig. Swap elements 2 and 5 , then move forward

Next, we move on to the next element 4in the unsorted portion of the array and compare it to the elements in the sorted portion of the array.
We swap 4with 5to get [2, 4, 5, 6, 1, 3].
We continue to move 4 to the left within the sorted portion of the array until it is in its correct position, resulting in [2, 4, 5, 6, 1, 3].

Fig. Swap elements 4 and 5, then move forward

We repeat this process for the remaining elements until the entire array is sorted.

Code Implementation

# remember: start with the **2nd element**
  # traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        target = arr[i]
        j = i - 1

        # arr[j] and arr[j + 1] are out of order, so swap them
        while j >= 0 and arr[j] > target:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = target

    return arr

## Important things to note

Insertion Sort has a worst-case time complexity of O(n²), which means it can become slow for very large lists.
It has some advantages over other sorting algorithms, such as being easy to implement and taking up very little memory.
It is also an “in-place” algorithm, meaning it modifies the original list rather than creating a new one.
Finally, it is a stable sorting algorithm, which means that it preserves the relative order of equal elements in the list.