Insertion Sort Algorithm Explained with Examples

The Insertion Sort algorithm is a simple and intuitive method used to arrange elements in a particular order from smallest to largest. It works much like how we sort cards in our hands, by taking one element at a time and placing it into its correct position relative to the already sorted elements before it. 

This process continues until the entire list is organized. Although it's not the most efficient option for handling large amounts of data, when the elements are in random order, it performs quite well when the list is nearly sorted or small in size. Due to its direct approach, it's used in educational settings to help beginners understand the basic principles behind sorting techniques.

Features of Insertion Sort

• Uses Original Array: It sorts the data within the same array, so no extra space is needed.
• Keeps Equal Items in Order: If two items are the same, their original order is preserved.
• Great for Small or Almost-Sorted Lists: It performs well when the list is short or nearly sorted.
• Time Complexity: Best Case (Already Sorted): Runs in linear time: O(n), Average and Worst Case: Slower, with quadratic time: O(n²)

The insertion sort algorithm organizes a list by gradually creating a sorted section, adding one item at a time in the correct position. Here's how it works in everyday terms:

• Start with the First Item: Think of the first element in the list as already sorted, since one item by itself doesn’t need sorting.
• Check at the Next Item (the "Key"): Move to the next item in the list. This is the one you're going to place in the correct position among the items you've already sorted.
• Compare with the Sorted Section: Go backwards through the already sorted part of the list. Compare the key with each item to find where it should go.
• Make Room by Shifting Items: If any item in the sorted part is larger than the key, move it one position to the right to make space.
• Insert the Key Where It Belongs: Once you find the right spot, where the key is no longer smaller than the item before it, insert it there.
• Repeat for Each Remaining Item: Go to the next unsorted item and repeat the steps until you reach the end of the list.

Pseudo Code for Insertion Sort Algorithm

INSERTION_SORT(array, n)
    for i ← 1 to n − 1 do
        key ← array[i]
        j ← i − 1

        while j ≥ 0 and array[j] > key do
            array[j + 1] ← array[j]
            j ← j − 1

        array[j + 1] ← key

Step-by-Step Illustrative Example: Sorting an Array 

In​‍​‌‍​‍‌​‍​‌‍​‍‌ order to grasp the working mechanism of insertion sort on the data, it is very helpful to go through a detailed example and picture the main steps as the method goes through the array. Assume that we are sorting the following array in ascending order:

[9, 5, 1, 4, 3]

Step 1: Start with the First Element

• The first element (9) is considered already sorted.
• Now, we take the second element (5) and compare it with 9.
• Compare 5 with 9
• Since 5 is smaller than 9, shift 9 to the right and place 5 before it.
• Updated array: [5, 9, 1, 4, 3]

Step 2: Insert 1 in the Correct Position

• Take the next element (1) and compare it with 9 and 5.
• Since 1 is smaller than both, shift 9 and 5 to the right and insert 1 at the beginning.
• Updated array: [1, 5, 9, 4, 3]

Step 3: Insert 4 in the Correct Position

• Take the next element (4) and compare it with 9 and 5.
• Since 4 is smaller, shift 9 and 5 to the right and place 4 in the correct position.
• Updated array: [1, 4, 5, 9, 3]

Step 4: Insert 3 in the Correct Position

• Take the last element (3) and compare it with 9, 5, and 4.
• Since 3 is smaller, shift 9, 5, and 4 to the right and insert 3 behind 1.
• Final sorted array: [1, 3, 4, 5, 9]

Key Takeaways

• Insertion​‍​‌‍​‍‌​‍​‌‍​‍‌ sort gradually creates a sorted part, placing each new element in its proper position.
• After every operation, picture the sorted and unsorted parts to grasp the algorithm's advancement.
• Using the cards analogy for sorting helps to easily understand the process and makes it ​‍​‌‍​‍‌​‍​‌‍​‍‌familiar. 

By following this step-by-step visualization, anyone can grasp how insertion sort organizes data, making the algorithm much easier to understand and remember.

The​‍​‌‍​‍‌​‍​‌‍​‍‌ Insertion Sort Algorithm logic is identical in all programming languages. The only difference is syntax; the core idea of taking one element, shifting larger elements, and inserting it in the correct position is the same.

Method 1: Iterative Implementation

With this method, loops are utilized to bring each element to its right place in the sorted part of the array. The method is space-efficient and is generally preferred by ​‍​‌‍​‍‌​‍​‌‍​‍‌developers.

C (Iterative)

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

C++ (Iterative)

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Java (Iterative)

static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Python (Iterative)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

JavaScript (Iterative)

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

Explanation of Iterative Insertion Sort

The iterative insertion sort builds the sorted array one element at a time, moving from left to right.

How the Code Works (Step-by-Step)

1. Start from the second element
   
   • The first element is already considered sorted.
   • The loop begins at index 1.
2. Store the current element as key
   
   • This is the element that needs to be placed in the correct position.
3. Compare with elements on the left
   
   • Move backward through the already sorted part of the array.
   • Compare each element with key.
4. Shift larger elements to the right
   
   • If an element is greater than key, shift it one position to the right.
   • This creates space for the key.
5. Insert the key
   
   • Once the correct position is found, place key there.
6. Repeat until the array is sorted
   
   • The process continues until all elements are inserted correctly.

Why This Works

At​‍​‌‍​‍‌​‍​‌‍​‍‌ every iteration, the insertion sort algorithm keeps the left side of the array sorted. It gradually extends this sorted part until the whole array is sorted.

Time and Space Complexity:

• Time Complexity: O(n²) in the worst and average case, O(n) in the best case (already sorted).
• Space Complexity: O(1), it sorts the array in place without using extra memory.

Method 2: Recursive Approach

This method sorts the array by recursively sorting smaller portions and inserting elements in order. It is conceptually clear but uses extra stack space.

C (Recursive)

void recursiveInsertionSort(int arr[], int n) {
    if (n <= 1) return;

    recursiveInsertionSort(arr, n - 1);

    int last = arr[n - 1];
    int j = n - 2;

    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

C++ (Recursive)

void recursiveInsertionSort(int arr[], int n) {
    if (n <= 1) return;

    recursiveInsertionSort(arr, n - 1);

    int last = arr[n - 1];
    int j = n - 2;

    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

Java (Recursive)

static void recursiveInsertionSort(int[] arr, int n) {
    if (n <= 1) return;

    recursiveInsertionSort(arr, n - 1);

    int last = arr[n - 1];
    int j = n - 2;

    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

Python (Recursive)

def recursive_insertion_sort(arr, n):
    if n <= 1:
        return

    recursive_insertion_sort(arr, n - 1)

    last = arr[n - 1]
    j = n - 2

    while j >= 0 and arr[j] > last:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = last

JavaScript (Recursive)

function recursiveInsertionSort(arr, n = arr.length) {
    if (n <= 1) return arr;
    recursiveInsertionSort(arr, n - 1);

    let last = arr[n - 1];
    let j = n - 2;

    while (j >= 0 && arr[j] > last) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;

    return arr;
}

Explanation of Recursive Insertion Sort (All Languages)

The recursive method splits a problem down into smaller components in order to solve it.

Core Idea

First, sort the first n-1 elements.
Then, insert the last element into its correct position.

How the Code Works (Step-by-Step)

1. Base Case
   
   • If the array size is 1 or less, it is already sorted.
   • The recursion stops here.
2. Recursive Call
   
   • The function calls itself to sort the first n-1 elements.
3. Insert the last element
   
   • Just take the last element (key) and compare it with the sorted portion.
   • Shift larger elements to the right
4. Place the key
   
   • Insert the key into its correct position.
5. Repeat through recursion
   
   • Each recursive call sorts the problem of a smaller size until the entire array is sorted.

Why This Works

The recursion guarantees that smaller portions are sorted first, thus inserting the remaining element becomes easy and ​‍​‌‍​‍‌​‍​‌‍​‍‌predictable.

Time and Space Complexity:

• Time Complexity: O(n²) in average and worst case, O(n) in best case (already sorted).
• Space Complexity: O(n) due to the recursive call stack.

Bottom Line 

Insertion sort logic is language-independent. If you understand how elements shift and insert, you can code it iteratively or recursively in any language.

Understanding the complexity analysis of insertion sort helps evaluate how the algorithm performs under different input conditions. This analysis focuses on time complexity, space complexity, and how performance depends on the nature of the input data.

Time Complexity Analysis (Big O Notation)

The time complexity of insertion sort depends heavily on the initial order of the input array, making it an input-dependent algorithm.

1. Best-Case Complexity – O(n)

• Happens when the array is already sorted or nearly sorted.
• Each element is compared once, and no shifting is required.
• This makes insertion sort very efficient for nearly sorted data.

2. Average-Case Complexity – O(n²)

• Occurs when elements are in random order.
• Each element is compared with roughly half of the sorted portion.
• The number of comparisons and shifts grows quadratically.

3. Worst-Case Complexity – O(n²)

• Happens​‍​‌‍​‍‌​‍​‌‍​‍‌ when the array is sorted in the opposite order.
• Every new element must be compared with all previous elements.
• This results in maximum shifts and comparisons.

Why is Insertion Sort Input Dependent

Insertion sort algorithm is a method that uses less work when the elements are already almost in their correct places. The input dependency is one reason why insertion sort can be faster than merge sort for small or nearly sorted ​‍​‌‍​‍‌​‍​‌‍​‍‌datasets.

Space Complexity Analysis

• Auxiliary Space: O(1) for the iterative version
• The algorithm sorts the array in place, requiring no extra data structures.
• This makes insertion sort a space-efficient sorting algorithm.

Note: Recursive insertion sort uses O(n) space due to the call stack.

Performance Summary Table

When Insertion Sort Performs Best

• Small datasets
• Nearly sorted data
• Memory-constrained environments
• Situations requiring stable sorting

Bottom Line 

Insertion sort method trades speed for simplicity: it is fast for small or nearly sorted inputs but inefficient for large, randomly ordered data.

Insertion​‍​‌‍​‍‌​‍​‌‍​‍‌ sort’s simplicity and special features allow it to be a valuable instrument in various local situations. Let’s explore further where and why insertion sort is typically utilized:

1. Sorting Small Data Sets

Insertion sort is extremely effective in the case of a small list of less than 10–20 elements. Because of its minimal overhead and the fact that it sorts in place, it can run faster than more complex algorithms on small arrays. 

• That is the reason why you can find it so often in embedded systems and microcontrollers, situations where data volumes are small and resources are limited.
• Quick single sorting in utility functions or ​‍​‌‍​‍‌​‍​‌‍​‍‌scripts. 

2. Maintaining Nearly Sorted Data

When a list is already mostly sorted, insertion sort quickly finds and places out-of-order elements with very few comparisons or shifts. This property is useful in:

• Real-time applications where data is updated incrementally, such as live leaderboard rankings or user interface lists that change slightly after each action. 
• Editing operations, like inserting or removing a few items from a sorted array.

3. Real-Time and Online Sorting

Insertion sort works with one element at a time and can efficiently insert new items into their correct position, so it’s the first choice for situations in which data is sequentially arriving:

• Event-driven systems or time-series data streams require maintaining a sorted order as new data points arrive.
• Buffer management in streaming applications, where maintaining a sorted buffer is necessary for processing. 

4. Subroutine in Hybrid Sorting Algorithms

Many sophisticated sorting algorithms, upon getting down to operating on small subarrays, make a call to insertion sort in order to capitalize on its effectiveness with tiny data sets and hence lower the total overhead. The instances are:

• TimSort and IntroSort employ insertion sort for instrumental parts during their recursive processes.
• Bucket sort, in which every bucket is sorted by means of insertion sort, because each bucket usually contains a small number of elements.

5. Educational Purposes and Coding Interviews

Insertion sort’s step-by-step logic and clear visualization make it a favorite in educational settings:

• Helping to learn fundamental concepts of algorithms, such as in-place sorting and algorithm stability.
• Coding interviews, where interviewers ask candidates to implement or analyze insertion sort to demonstrate understanding of basic sorting mechanics.

Knowing these practical applications will empower you with the knowledge of the exact time and the reason for venturing into insertion sort in programming scenarios of the real ​‍​‌‍​‍‌​‍​‌‍​‍‌world. 

Advantages:

• Simple to Code and Understand: The process is clear, hence coding the algorithm and debugging it will be a simple task.
• No Extra Memory Needed: Insertion sort doesn’t require any additional storage; it rearranges items within the original list.
• Performs Well on Nearly Ordered Data: If the list is already close to being sorted, insertion sort is very fast, usually needing very few comparisons and swaps.
• Keeps Equal Items in Order: The algorithm is a stable one, thus if two elements are equal, their original order will be retained in the sorted ​‍​‌‍​‍‌​‍​‌‍​‍‌list. 

Disadvantages:

• Too Slow for Large Lists: The Insertion Sort Algorithm is a method that becomes inefficient as the size of the dataset grows. Its approach involves comparing each element with a multitude of other elements, thus the time complexity of the operation is O(n²), which makes the method unusable for large ​‍​‌‍​‍‌​‍​‌‍​‍‌tasks.
• Not Suitable for Parallel Processing: Insertion sort is a sequential algorithm; it processes one item at a time, so it's not well-suited for parallel computing or high-performance systems where multiple tasks are run simultaneously.

Insertion​‍​‌‍​‍‌​‍​‌‍​‍‌ Sort is the one that most closely simulates human behavior as it literally puts the new element in the already sorted portion exactly where it belongs. What makes it famous is not the speed with which it can handle big datasets, but the clarity, being stable and efficient on data that are almost sorted. Working on it in different programming languages, you realize that algorithms are a matter of logic, not syntax. Learning insertion sort will make your algorithmic thinking stronger and will be a good way to have a background when you want to move on to more advanced sorting techniques and eventually optimize them.

Points to Remember

1. Insertion​‍​‌‍​‍‌​‍​‌‍​‍‌ sort constructs a sorted subarray one element at a time from the left side, placing each new element in its correct position.
2. As it shifts elements rather than swapping, this is the reason that it stays a stable sorting algorithm.
3. The method picks the second element as the starting point and considers the first element to be already sorted.
4. The best-case time complexity is O(n) when the array is sorted or almost sorted; therefore, the algorithm is adaptive.
5. An iterative insertion sort takes up constant extra space, whereas a recursive one requires additional stack ​‍​‌‍​‍‌​‍​‌‍​‍‌memory. 

1. What does insertion sort do?

The algorithm sequentially traverses the array. It goes through the list one by one, and for each new element, it finds the appropriate position among the already sorted elements, shifting the bigger ones to create a place.

2. Is insertion sort stable?

Yes, it keeps items with the same value in their original order.

3. When is insertion sort a good choice?

It works well on small lists or when the list is mostly sorted already.

4. Can you use recursion with insertion sort?

Yes, you can write it recursively by sorting the smaller part first, then placing the next item where it belongs.

5. How does it compare to other sorting methods?

It’s easier to understand and use, but not great for large lists since it’s slower than more advanced algorithms like Quick Sort or Merge Sort.