What is Insertion Sort?

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It works similarly to the way you might sort playing cards in your hands. It builds the sorted array (or list) one element at a time by comparing each new element with the elements already sorted and inserting it into the correct position. The algorithm maintains a sorted sublist in the lower positions of the array and progressively inserts the remaining unsorted elements into their correct positions.

How Insertion Sort Works ?

Insertion Sort works by iterating over the array and inserting each element into its correct position relative to the already sorted portion of the array.

Step-by-step explanation:

1. Start from the second element (the first element is already sorted by itself).
2. Compare the current element with the elements before it.
3. If the current element is smaller than the element before it, shift the larger element one position to the right.
4. Insert the current element at its correct position.
5. Repeat this process for each element until the entire array is sorted.

Example of Insertion Sort

Let’s take an example of sorting the array [12, 11, 13, 5, 6]:

1. Initial List: [12, 11, 13, 5, 6]
2. First Pass (11):
   • Compare 11 with 12. Since 11 is smaller, move 12 to the right and place 11 in the first position.
   • Result: [11, 12, 13, 5, 6]
3. Second Pass (13):
   • Compare 13 with 12. Since 13 is larger, no change is needed.
   • Result: [11, 12, 13, 5, 6]
4. Third Pass (5):
   • Compare 5 with 13, 12, and 11. Shift all of them to the right and place 5 in the first position.
   • Result: [5, 11, 12, 13, 6]
5. Fourth Pass (6):
   • Compare 6 with 13, 12, and 11. Shift 13 and 12 to the right, and place 6 after 5.
   • Result: [5, 6, 11, 12, 13]

Now, the array is sorted.

C++ Program to implement Insertion Sort Algorithm

#include <iostream>
using namespace std;

// Function to perform insertion sort
void insertionSort(int arr[], int n) {
    // Traverse the array starting from the second element (index 1)
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // The element to be placed in its correct position
        int j = i - 1;

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

        // Place the key at its correct position
        arr[j + 1] = key;
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

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

    cout << "Original array: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Java Program to implement Insertion Sort Algorithm

public class Main {
    // Function to perform insertion sort
    public static void insertionSort(int arr[]) {
        int n = arr.length;

        // Traverse the array starting from the second element (index 1)
        for (int i = 1; i < n; i++) {
            int key = arr[i];  // The element to be placed in its correct position
            int j = i - 1;

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

            // Place the key at its correct position
            arr[j + 1] = key;
        }
    }

    // Function to print the array
    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Main function
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6};

        System.out.println("Original array:");
        printArray(arr);

        insertionSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Python Program to implement Insertion Sort Algorithm

# Function to perform insertion sort
def insertion_sort(arr):
    # Traverse the array starting from the second element (index 1)
    for i in range(1, len(arr)):
        key = arr[i]  # The element to be placed in its correct position
        j = i - 1

        # Shift elements of arr[0..i-1] that are greater than key
        # to one position ahead of their current position
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Place the key at its correct position
        arr[j + 1] = key

# Function to print the array
def print_array(arr):
    print(" ".join(map(str, arr)))

# Main function
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6]

    print("Original array:")
    print_array(arr)

    insertion_sort(arr)

    print("Sorted array:")
    print_array(arr)

Properties of Insertion Sort

• Time Complexity:
  • Best Case: O(n) - when the array is already sorted.
  • Average Case: O(n²)
  • Worst Case: O(n²) - when the array is sorted in reverse order.
• Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm.
• Stability: Insertion Sort is a stable sorting algorithm, meaning it maintains the relative order of equal elements.
• Adaptability: Insertion Sort is adaptive. If the array is already sorted (or nearly sorted), it performs efficiently with fewer comparisons and swaps.

When to Use Insertion Sort ?

Insertion Sort is generally more efficient for small datasets or for datasets that are already mostly sorted. It is also used in hybrid algorithms, like Timsort, as a sorting mechanism for small subarrays.

Frequently Asked Questions (FAQs) about Insertion Sort Algorithm

Q1: What is the time complexity of Insertion Sort?

• A: The time complexity of Insertion Sort is O(n²) in the average and worst cases, and O(n) in the best case when the array is already sorted.

Q2: Is Insertion Sort a stable sorting algorithm?

• A: Yes, Insertion Sort is a stable sorting algorithm because it preserves the relative order of elements with equal values.

Q3: What is the space complexity of Insertion Sort?

• A: The space complexity of Insertion Sort is O(1), as it sorts the array in-place without using additional memory.

Q4: When is Insertion Sort efficient?

• A: Insertion Sort is efficient for small datasets and arrays that are already (or nearly) sorted. It is also adaptive, meaning it performs well when the data is partially sorted.

Q5: How does Insertion Sort compare to Bubble Sort and Selection Sort?

• A: Insertion Sort is generally more efficient than both Bubble Sort and Selection Sort for small arrays and nearly sorted data. While all three algorithms have a time complexity of O(n²) in the worst case, Insertion Sort has a best-case time complexity of O(n) when the array is already sorted.