What is Insertion Sort?¶

Insertion Sort is a simple and intuitive sorting algorithm. Its core idea is similar to how we sort playing cards: inserting a new card into the correct position in an already sorted pile until all cards are ordered. In computers, this means inserting each element of the array into its proper position within the already sorted subarray before it, until the entire array is sorted.

Basic Idea of Insertion Sort¶

Suppose we have an array arr and want to sort it in ascending order. The steps are as follows:

1. Initial State: The first element (index 0) is by default “sorted” because a single element is inherently ordered.
2. Insert One by One: Starting from the second element (index 1), process each element sequentially:
   - Take the current element arr[i] and temporarily store its value (to avoid overwriting during subsequent element shifts).
   - Compare from the end of the sorted subarray (i.e., position i-1) backwards: if the preceding element arr[j] is greater than the current element, shift arr[j] one position to the right (to make space).
   - Repeat the comparison and shifting until an element arr[j] is found that is smaller than the current element. Insert the temporarily stored element at position j+1.
3. Termination: After processing all elements, the array is naturally sorted.

Algorithm Implementation Steps (C++ Code)¶

Here’s the code implementing the above logic, with comments explaining each step:

#include <iostream>
using namespace std;

// Insertion Sort function: takes array arr and its length n
void insertionSort(int arr[], int n) {
    // Outer loop: start from the second element (i=1) to the end (i=n-1)
    for (int i = 1; i < n; i++) {
        int temp = arr[i];  // Temporarily store the current element to insert
        int j = i - 1;      // j points to the last element of the sorted subarray

        // Inner loop: compare backwards to find the insertion position
        // Condition: j >= 0 (not out of bounds) and arr[j] > temp (preceding element is larger)
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];  // Shift the preceding element right
            j--;                  // Move left to continue comparison
        }

        // Insert the temporarily stored element into its correct position
        arr[j + 1] = temp;
    }
}

int main() {
    // Test case: array to be sorted
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);  // Calculate array length

    // Print the array before sorting
    cout << "Before sorting: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Call insertion sort function
    insertionSort(arr, n);

    // Print the array after sorting
    cout << "After sorting: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Code Logic Explanation¶

1. Outer Loop (Processing Each Element to Insert)¶

• Starts at i=1 (since index 0 is initially sorted).
• For each i, the current element arr[i] is identified and needs to be placed in the correct position within the sorted subarray.

2. Inner Loop (Finding the Insertion Position)¶

• temp = arr[i]: Temporarily stores the current element to prevent overwriting during shifts.
• j = i - 1: Starts from the end of the sorted subarray and moves leftwards.
• while (j >= 0 && arr[j] > temp):
• If the preceding element arr[j] is larger than temp, shift arr[j] right by one position (arr[j+1] = arr[j]).
• Decrement j to continue comparing with the next preceding element.
• When the loop exits, j+1 is the correct position for temp, so arr[j+1] = temp.

Example: Manual Simulation of the Sorting Process¶

Take the array [5, 2, 4, 6, 1, 3] to demonstrate the sorting step-by-step:

1. Initial Array: [5, 2, 4, 6, 1, 3] (sorted subarray: [5])
2. Processing i=1 (element 2):
   - temp=2, j=0 (end of sorted subarray).
   - arr[j]=5 > 2, so arr[1] = 5, j=-1.
   - Insertion result: arr[0]=2 → [2, 5, 4, 6, 1, 3].
3. Processing i=2 (element 4):
   - temp=4, j=1 (end of sorted subarray is 5).
   - arr[j]=5 > 4, so arr[2] = 5, j=0 (arr[j]=2 <= 4).
   - Insertion result: arr[1]=4 → [2, 4, 5, 6, 1, 3].
4. Subsequent Steps: Continue processing i=3 (6), i=4 (1), i=5 (3). The final sorted array is [1, 2, 3, 4, 5, 6].

Complexity Analysis¶

• Time Complexity:
• Worst Case: When the array is reverse-sorted (e.g., [5,4,3,2,1]), O(n²) comparisons and shifts are needed.
• Best Case: When the array is already sorted (e.g., [1,2,3,4,5]), the inner loop only requires 1 comparison, resulting in O(n) time.
• Space Complexity: Only temporary variables (temp) are used, so O(1) (in-place sorting).

Applicable Scenarios¶

Insertion Sort is suitable for small datasets (e.g., n < 1000) or nearly sorted data (where it approaches O(n) efficiency). Its advantages include simplicity, intuitiveness, and stability (preserving the relative order of equal elements). However, for large datasets, it is less efficient than advanced algorithms like Quick Sort or Merge Sort.

Summary¶

The core of Insertion Sort is “inserting one element at a time” into the correct position within the already sorted subarray. In C++, this is implemented with two nested loops (outer for traversal, inner for shifting). Despite its simplicity, attention must be paid to boundary conditions (e.g., handling j=-1) and temporary variable usage to avoid data loss. Mastering Insertion Sort is foundational for understanding more complex sorting algorithms.