Skip to content

What Is Insertion Sort and How Does It Work? The Ultimate Guide

Insertion sort is one of the most foundational sorting algorithms in computer science. In this comprehensive 2500+ word guide, we’ll unpack exactly what insertion sort is, how it arranges data, and the concepts that make it vital for every developer to know.

Overview of Insertion Sort

Insertion sort iterates through an array, growing a sorted output list. It works analogously to sorting a hand of playing cards by moving higher cards one spot right. This simplicity contributes to fast speed and stability for small and mostly-ordered data sets.

We’ll be exploring the insertion sort step-by-step, implementing it in Python, and combining visuals with technical analysis. The goal is a reference guide for understanding this ubiquitous sorting technique inside and out!

What Is Insertion Sort?

Insertion sort is an in-place comparison sort algorithm that builds a final sorted array one element at a time — as if inserting cards by value into an empty sorted deck.

As Princeton’s algorithm textbook describes it, ”insertion sort iterates, consuming one input element each repetition, and grows a sorted output list.”

How Insertion Sort Works at a High Level

  1. Start with an empty left hand: the sorted deck
  2. Select the first unsorted card: the next unsorted element
  3. Insert into the sorted deck by shifting higher cards to the right
  4. Repeat steps 2-3 until no unsorted cards remain

By working through the array shifting elements from left to right with each insertion rather than swapping globally, insertion sorts operates in-place without requiring significant extra memory.

Comparing Insertion Sort to Other Simple Sorts

Insertion sort distinguishes itself from similar introductory algorithms like:

  • Selection sort – Finds minimum value each pass to swap with leftmost unsorted position
  • Bubble sort – Compares adjacent elements and swaps them if out of order

The shifting approach of insertion sort maintains stability; the relative order of duplicates is unchanged. This adaptability contributes to blazingly fast performance on small and mostly-sorted data as well.

How Does the Insertion Sort Algorithm Work?

Insertion sort iterates through an array one element at a time, inserting each into the final sorted output by shifting larger elements to the right.

Let‘s walk step-by-step through the pseudocode to solidify comprehension:

insertionSort(A)
for i ← 1 to length(A)
    x ← A[i]
    j ← i - 1
    while (j >= 0 && A[j] > x)
        A[j + 1] ← A[j] 
        j ← j - 1
    end while
    A[j + 1] ← x
end for

Breaking this down:

  1. Starting with the 2nd element (at index 1), assign it to x
  2. Compare x to the element to its left in the array, storing that index in j
  3. Shift any greater elements (A[j] > x) one index to the right
  4. When we find a smaller/equal element, insert x in that position

By repeating steps 2-4 as we move rightwards, the sorted array is built up element by element!

Insertion Sort By Example

Now let‘s explore insertion sort with a concrete array example. Consider the initial array [20, 5, 40, 60, 45].

Pass 1:

Start with 20 as first "sorted" element

Array: [20, 5, 40, 60, 45]

Pass 2:

Compare 5 to 20. Insert 5 before 20 by shifting 20 right.

Array: [5, 20, 40, 60 45]

Pass 3:

Insert 40 after 20 by leaving it in place.

Array: [5, 20, 40, 60, 45]

Pass 4:

60 is after the last sorted element, so it remains unsorted.

Array: [5, 20, 40, 60, 45]

Pass 5:

Finally insert 45 after 40 by shifting others right.

Final Sorted Array: [5, 20, 40, 45, 60]

Observe how the subarray on the left fills up one element at a time until sorted!

Analyzing Insertion Sort Complexity

We evaluate sorting algorithms using Big O Notation across time and space complexity metrics. This quantifies performance across worst/average/best case input.

Time Complexity
| Case | Complexity |
| —- | ——– |
| Best Case | O(n) |
| Average Case | O(n^2) |
| Worst Case | O(n^2) |

Space Complexity

  • O(1) constant

With each insertion made in-place by shifting right, minimal additional memory is needed. Insertion sort is extremely fast when n is small, making it well-suited for sorting sublists. But performance slows quadratically as input size increases due to shifting overhead.

Implementation of Insertion Sort in Python

Here is an implementation of insertion sort in Python to solidify concepts:

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

array = [5, 2, 9, 1, 67]
insertion_sort(array)
print(array) # [1, 2, 5, 9, 67]

Breaking down the key aspects:

  • Set key as next unsorted element
  • Compare key to each leftward element
  • Shift larger elements to the right
  • When smaller element found, insert key

This demonstrates insertion sort simply in Python. Next let‘s explore optimizations and applications.

Optimizing Insertion Sort

Binary Insertion Sort modifies the algorithm to leverage binary search in locating the insertion point rather than sequential search. This yields a best case complexity of O(n log n).

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  
        lower = 0
        upper = i-1
        while lower <= upper:  
            mid = (lower + upper) // 2  
            if arr[mid] < key :
                lower = mid + 1 
            else: 
                upper = mid - 1
        j = upper
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]   
            j-=1
        arr[j+1] = key

Rather than comparing against every leftward element, we leverage binary search to hone in on the insertion point logarithmically.

When Should Insertion Sort Be Used?

Insertion sort works best on:

  • Small data sets – optimized for fast sorting of subsets under 100 elements
  • Streaming data – can sort new elements "on the fly" as they arrive
  • Partially sorted arrays – adaptive and stable nature
  • Stable sort required – preserves equivalence class ordering

For larger disordered data, performant algorithms like quicksort and heapsort are generally preferred.

Insertion sort will shine when simplicity, stability, and speed for almost-sorted tiny sets are desired. As an early sorting technique, insertion sort establishes core procedural concepts for novice programmers.

The History Behind Insertion Sort

Insertion sort originated from research on optimizing computer memory usage at University of Manchester in 1945. Developer John Backus implemented insertion sort as part of the Speedcoding system for early IBM computers in the 1950’s.

It entered computer science literature through Newell, Shaw, and Simon’s 1957 algorithm proof – one of the first analyses of computational complexity.

While less performant than mergesort and quicksort due to its O(n^2) comparisons, insertion sort’s approachability played a key role in classical sorting evolution.

Limitations of Insertion Sort

The primary limitations of insertion sort relate to its quadratic time complexity on average and worst cases. As input size grows large, performance slows significantly from the overhead of shifting elements repeatedly.

Algorithms like quicksort and heapsort utilizing more complex sorting approaches like divide-and-conquer provide better raw speed. Mergesort and timsort leverage merging of pre-sorted groups as well.

So while excellent for smaller sets and teaching sorting basics, insertion sort becomes impractical for many production use cases. Hybrid sorting methods combining algorithms can optimize for hardware capabilities and dataset characteristics. Python‘s Timsort and Java Array‘s merge/insertion sort hybrid demonstrate the power of blended approaches.

Conclusion & Final Thoughts

I hope this guide solidified exactly how the elegant insertion sort algorithm builds up a sorted array by incrementally shifting elements on each pass.

Insertion sort plays a foundational role in computer science education by demonstrating core iterative sorting techniques with approachable code.

Its speed and stability signatures make insertion sort shine for small and mostly-sorted data critical for larger algorithms. While asymptotic limits exist, adaptations like binary insertion sort aim to stretch capabilities.

Continued combinatorial optimizations and hardware advances will further refine sorting frontiers. But inserting cards in your hand provides a mental model to conceptualize foundational iteration behind efficient ordering.

I aimed to thoroughly explain insertion sort fundamentals while surfacing key academic research and examples. Please let me know any feedback to improve future guides!

Tags: