Insertion Sort Data Structures Notes 2025 with Examples for Engineering

Introduction to Insertion Sort

Insertion Sort is one of the simplest and most intuitive sorting algorithms studied in B.Tech Data Structures Notes 2025 and is often taught early in courses related to algorithm design. It belongs to the class of comparison-based sorting techniques and mimics the way one might sort playing cards in their hand. The algorithm builds the final sorted array one element at a time, by comparing each new element with those already sorted and inserting it at the correct position. This method is in-place and stable, meaning it requires no additional space apart from the input array and maintains the relative order of equal elements.

Working Principle of Insertion Sort

The core idea of Insertion Sort lies in dividing the list into two parts: the sorted portion and the unsorted portion. Initially, the first element is considered sorted. The algorithm then picks each subsequent element from the unsorted section and inserts it into its appropriate position in the sorted part by comparing it with the elements already present. This continues until all the elements are placed correctly, resulting in a fully sorted array. The efficiency of this algorithm greatly depends on the initial ordering of the elements.

Algorithm Steps

Start with the second element (index 1) since the first is trivially sorted.
Compare the current element (key) with the elements before it.
Shift all larger elements one position to the right.
Insert the key at its correct position.
Repeat until the end of the array is reached.

Pseudocode for Insertion Sort

procedure insertionSort(A: array of items)
   for i = 1 to length(A) - 1
       key = A[i]
       j = i - 1
       while j >= 0 and A[j] > key
           A[j + 1] = A[j]
           j = j - 1
       A[j + 1] = key

Illustrative Example of Insertion Sort

Let us sort the array A = [5, 3, 4, 1, 2] using insertion sort.

Step 1: Initially sorted: [5], unsorted: [3, 4, 1, 2] → Insert 3 → [3, 5] Step 2: [3, 5], Insert 4 → [3, 4, 5] Step 3: [3, 4, 5], Insert 1 → [1, 3, 4, 5] Step 4: [1, 3, 4, 5], Insert 2 → [1, 2, 3, 4, 5]

Final Sorted Array: [1, 2, 3, 4, 5]

📌 Insert Diagram: Insertion Sort Working Flowchart

Dry Run of the Algorithm

For array: [9, 5, 1, 4, 3]

Pass 1: key = 5, compare with 9 → shift 9 → insert 5 → [5, 9, 1, 4, 3] Pass 2: key = 1, compare with 9 and 5 → shift both → insert 1 → [1, 5, 9, 4, 3] Pass 3: key = 4, shift 9 and 5 → insert 4 → [1, 4, 5, 9, 3] Pass 4: key = 3, shift 9, 5, 4 → insert 3 → [1, 3, 4, 5, 9]

Time Complexity Analysis

Best Case (Already Sorted): O(n) — Only one comparison per element
Average Case: O(n^2) — Every element compared with all others before it
Worst Case (Reverse Sorted): O(n^2) — Maximum number of comparisons and shifts

Space Complexity: O(1) — In-place sorting

Stability: Insertion Sort is a stable sorting algorithm as it does not change the relative order of equal elements.

Use Cases of Insertion Sort

Sorting small datasets where simplicity matters more than performance
Useful when the data is nearly sorted (adaptive behavior)
Ideal for real-time systems where low overhead is important

Advantages of Insertion Sort

Simple to implement and understand
Efficient for small or nearly sorted data
Requires no additional memory space
Stable sort

Disadvantages of Insertion Sort

Poor performance on large datasets
Inefficient compared to advanced algorithms like Merge Sort or Quick Sort

Comparison with Other Sorting Algorithms

Algorithm	Time Complexity (Best)	Time Complexity (Worst)	Space Complexity	Stability
Insertion Sort	O(n)	O(n^2)	O(1)	Yes
Bubble Sort	O(n)	O(n^2)	O(1)	Yes
Selection Sort	O(n^2)	O(n^2)	O(1)	No
Merge Sort	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n^2)	O(log n)	No

Real-World Analogy

Imagine you are arranging books on a shelf by height. You take one book at a time and place it in the correct spot among the already arranged books. This is how insertion sort behaves — each book (element) is placed in its appropriate position by comparing with its left neighbors.

Variants of Insertion Sort

Binary Insertion Sort: Uses binary search to find the correct position to insert, reducing comparisons but not swaps.
List Insertion Sort: Applied to linked lists where insertion is less costly than shifting.
Shell Sort: Generalization of insertion sort that improves performance using gap sequences.

Code Implementation (C Language)

#include <stdio.h>

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

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printArray(arr, n);
    return 0;
}

🔹 Short Answer Questions (2–3 Marks)

Define Insertion Sort. → Insertion Sort is a comparison-based algorithm that builds the final sorted array one item at a time by inserting elements into their correct position.
State the best-case time complexity of Insertion Sort. → The best-case time complexity is O(n).
Is Insertion Sort a stable sorting algorithm? → Yes, it preserves the relative order of equal elements.
When is Insertion Sort preferred over other sorting algorithms? → It is preferred when dealing with small or nearly sorted datasets.
What is the space complexity of Insertion Sort? → The space complexity is O(1).
Does Insertion Sort work well with linked lists? → Yes, especially in its list-based variant.
Why is Insertion Sort called adaptive? → Because it adapts and performs better when the input is already partially sorted.

🔸 Long Answer Questions (5–10 Marks)

Explain the working of Insertion Sort with a dry run on the array [7, 2, 4, 9, 1]. → Include full explanation with shifts and comparisons.
Compare Insertion Sort with Selection and Bubble Sort in terms of stability and time complexity. → Provide tabular comparison and elaboration.
Write and explain the Insertion Sort algorithm with proper pseudocode. → Provide line-by-line explanation of logic.
Describe the advantages and disadvantages of Insertion Sort in real-world applications. → Mention where it fits in modern computing.
Explain how binary search improves the Insertion Sort. Describe Binary Insertion Sort. → Discuss time complexity and insertion method changes.

📝 Chapter Summary Insertion Sort is a simple comparison-based algorithmIt works by inserting elements into the sorted part of the array one by oneIt has O(n^2) time complexity in the worst case but O(n) in the best caseIt is stable and in-place making it memory-efficientIt works best on small or nearly sorted datasetsIts variants include Binary Insertion Sort and Shell SortIt is included in Unit 2 Notes Data Structures for B.Tech and BCA students

📘 Model Paper / Sample Internal Exam Questions