Insertion Sort

Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time.

It is similar to how we sort playing cards in our hands: we pick one card at a time and insert it into its correct position among the already sorted cards.

How Insertion Sort Works?

• Start from the second element (index 1).
• Compare it with the element(s) before it.
• Shift all larger elements one position ahead.
• Insert the current element in its correct position.

This process is repeated for each element in the array.

Example: Insertion Sort

Sorting the array [5, 3, 8, 6, 2] using Insertion Sort

We will sort this array step-by-step, just like how you would sort playing cards in your hand.

Initial Array: [5, 3, 8, 6, 2]

We start from the second element (index 1) and move forward one element at a time.

Pass 1 (i = 1)

• Key = 3
• Compare with previous element 5
• Since 3 < 5, shift 5 to the right
• Insert 3 in the correct position

Array becomes: [3, 5, 8, 6, 2]

Pass 2 (i = 2)

• Key = 8
• Compare with 5 → 8 > 5 → already in the right place

No change: [3, 5, 8, 6, 2]

Pass 3 (i = 3)

• Key = 6
• Compare with 8 → 6 < 8, shift 8
• Compare with 5 → 6 > 5, stop
• Insert 6 after 5

Array becomes: [3, 5, 6, 8, 2]

Pass 4 (i = 4)

• Key = 2
• Compare with 8 → 2 < 8, shift 8
• Compare with 6 → 2 < 6, shift 6
• Compare with 5 → 2 < 5, shift 5
• Compare with 3 → 2 < 3, shift 3
• Now insert 2 at the beginning

Array becomes: [2, 3, 5, 6, 8]

Final Sorted Array: [2, 3, 5, 6, 8]

Summary of Each Pass

Algorithm for Insertion Sort

Here is a step-by-step algorithm for Insertion Sort, written in a clear and beginner-friendly way.

Step 1: Start
Step 2: Repeat steps 3 to 7 for i = 1 to length of array - 1
Step 3:     Set key = array[i]
Step 4:     Set j = i - 1
Step 5:     While j >= 0 AND array[j] > key, repeat:
Step 6:         Set array[j + 1] = array[j]
Step 7:         Set j = j - 1
Step 8:     Set array[j + 1] = key
Step 9: End

• Begin from the second element in the array.
• Store the current element in a variable called key.
• Compare the key with each element before it (in the sorted part of the array).
• Shift every larger element one position to the right.
• Insert the key into its correct sorted position.
• Repeat for all elements.

Advantages

The advantages of this sorting algorithm are as follows:

• Simple and easy to implement.
• Efficient for small data sets.
• Stable sort (preserves order of equal elements).
• Performs well for nearly sorted arrays (Best Case: O(n)).

Disadvantages

• Not suitable for large datasets.
• Inefficient compared to O(n log n) algorithms like Merge Sort or Quick Sort.

When to Use Insertion Sort

• When the dataset is small.
• When the dataset is nearly sorted.
• When stability is required.
• As part of hybrid algorithms (like TimSort and IntroSort) for sorting small subarrays.

Insertion Sort in C Programming

#include <stdio.h>

// Function to perform insertion sort
void insertionSort(int array[], int size) {
    int i, key, j;

    // Loop through each element starting from index 1
    for (i = 1; i < size; i++) {
        key = array[i];      // Current element to be inserted
        j = i - 1;

        // Move elements of array[0..i-1] that are greater than key
        // to one position ahead of their current position
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j = j - 1;
        }

        array[j + 1] = key;   // Insert the key at the correct position
    }
}

// Function to print the array
void printArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

// Main function
int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array:\n");
    printArray(arr, n);

    return 0;
}

Output:

Original array:
5 3 8 6 2
Sorted array:
2 3 5 6 8

Time and Space Complexity of Insertion Sort

If the initial tile is sorted, only one comparison is made on each iteration, so that the sort is O(n).

If the file is initially sorted in the reverse order the worst case complexity is O(n²).

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

Insertion Sort may not be the fastest sorting algorithm for large datasets, but its simplicity, stability, and efficiency for small or nearly sorted data make it a valuable tool. It’s often used in practice as a building block for more complex algorithms.

Numerical Question for Insertion Sort

1. Sort the array using insertion sort and write the array after each pass: [9, 7, 5, 3, 1]
2. For the array: [4, 3, 2, 1]
   • How many comparisons are made?
   • How many shifts (movements) are made during sorting?
3. What will be the number of comparisons and shifts for this input: [6, 5, 4, 3, 2, 1]
4. Sort the array and show the number of comparisons: [1, 2, 5, 3, 4]