Insertion Sort

Time Complexity

Space Complexity

Overview

Insertion sort is a simple sorting algorithm that builds a sorted list one element at a time by comparison (we will learn the alternative to comparison in other sections). It works by iterating through the input list and inserting each element into its proper position in the already sorted part of the list. The algorithm maintains a growing sorted sublist and repeatedly takes the next element from the unsorted part, finds its correct position in the sorted part, and inserts it there. This process continues until all elements are part of the sorted sublist, and the original list is completely sorted.

If the description so far sounds a bit confusing - look at the animation. The blue boxes are not sorted, the yellow/orange boxes are in action and the green boxes are sorted. When we have a sorted sublist (the green boxes to the left), we pick the leftmost unsorted element from the blue boxes and insert it in the correct position of the sorted greens.

Let's now proceed by explaining the exact input we have, [7, 3, 2, 6, 4, 5, 1], to demonstrate how insertion sort works step-by-step:

1. Initial state: [7, 3, 2, 6, 4, 5, 1] (the first element 7 is considered the sorted sublist)
2. Take the second element (3) and insert it into the sorted sublist by comparing it to the first element, resulting in: [3, 7, 2, 6, 4, 5, 1]
3. In the same way, take the next third element (2) and insert it into the sorted sublist (by comparing to 7 and to 3): [2, 3, 7, 6, 4, 5, 1]
4. Continue with the process - take the fourth element (6) and insert it into the sorted sublist: [2, 3, 6, 7, 4, 5, 1]
5. Take the fifth element (4) and insert it into the sorted sublist: [2, 3, 4, 6, 7, 5, 1]
6. Take the sixth element (5) and insert it into the sorted sublist: [2, 3, 4, 5, 6, 7, 1]
7. Take the seventh element (1) and insert it into the sorted sublist: [1, 2, 3, 4, 5, 6, 7]

Now the input list is sorted in ascending order using the insertion sort algorithm.

The algorithm's time complexity is O(n^2) in the worst case, where 'n' is the number of elements in the list. It's obviously not the most efficient sorting algorithm for large datasets, but let's take a look at its advantages first:

Advantages:

• Simplicity: It's very easy to learn and is a great one to start your journey in algorithms and data structures!
• Efficiency: It performs very well on partially sorted lists because it takes advantage of the existing order, minimizing the number of comparisons and swaps needed.
• In-Place Sorting: The elements are sorted directly in the original array, without the need for additional data structures.
• Stability: The order of equal values is maintained after sorting. Algorithms like HeapSort (which you will learn in later sections) don't do that. It's usually not a problem, but in some cases, the original order of the equal elements is important.

Now, let's look at its disadvantages:

Disadvantages:

• Inefficiency with large datasets: The already mentioned time complexity of O(n^2) takes its toll on large datasets, and the algorithm becomes rapidly slower.
• Bad for complex datasets: There's a lot of movement in the algorithm (though it looks cool in animation 😄) so it could be even more inefficient for more complex data (for instance, linked lists where we need to adjust the link between each node after movement).
• Very bad for reverse ordered data: If we end up using Insertion Sort on a reverse-sorted large dataset, it will perform the most possible comparisons and will be unusably inefficient.
• It uses comparison: Obviously, it uses comparison! Other algorithms that we will learn in the next sections also do that (so we won't mention it again explicitly). Why is it a bad thing? Comparison is a simple 'mechanical' arithmetic which is not bad. But simply using comparison doesn't utilize the advantages of the type of data it's going to sort. For instance, some non-comparison algorithms (like Counting Sort) perform really well on fixed and expected lengths of data, and others (like Heap Sort) use the Heap properties for sorting instead of comparison. Don't worry if these other algorithms don't mean much to you yet; you will get there in the next sections!

Code

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
 
# Example usage:
arr = [7, 3, 2, 6, 4, 5, 1]
insertion_sort(arr)
print(arr)  # Output: [1, 2, 3, 4, 5, 6, 7]
 

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
 
// Example usage:
let arr = [7, 3, 2, 6, 4, 5, 1];
insertionSort(arr);
console.log(arr); // Output: [1, 2, 3, 4, 5, 6, 7]
 

public class InsertionSort {
    public static 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;
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {7, 3, 2, 6, 4, 5, 1};
        insertionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // Output: 1 2 3 4 5 6 7
    }
}
 

#include <stdio.h>
 
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
 
int main() {
    int arr[] = {7, 3, 2, 6, 4, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    // Output: 1 2 3 4 5 6 7
    return 0;
}
 

function insertionSort(&$arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $key < $arr[$j]) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}
 
$arr = array(7, 3, 2, 6, 4, 5, 1);
insertionSort($arr);