Pseudocode of Insertion sort with Time Complexity Analysis

Insertion Sort is a simple sorting algorithm that picks an element from the unsorted position and inserts it into its correct position in the array. This algorithm works by comparing the current element with the elements before it. And shifting them to the right until the correct position is found.

Quescol 1-Minute Read

Insertion Sort is a simple and easy-to-understand sorting algorithm that picks one element at a time from the unsorted part and places it in its correct position within the sorted part of the list. It works just like how we arrange playing cards in order — taking one card at a time and putting it where it fits best. This algorithm is efficient for small or nearly sorted datasets but becomes slow for large or completely unsorted arrays. It performs sorting in place and maintains the relative order of equal elements, making it stable.

Insertion sort important Points:

• Works like arranging cards in order.
• Starts from the second element and inserts it in the correct position.
• Shifts larger elements to make space for the current element (key).
• In-place algorithm: doesn’t use extra memory (Space Complexity: O(1)).
• Stable sorting: maintains the order of equal elements.
• Adaptive: performs faster on nearly sorted data.
• Time Complexity:
  • Best Case – O(n)
  • Average Case – O(n²)
  • Worst Case – O(n²)
• Space Complexity: O(1) in all cases.
• Efficient for small datasets but inefficient for large data.

Let’s Understand in Depth

What is Insertion Sort?

Insertion Sort is a sorting algorithm that arranges elements in a specific order, such as ascending or descending. It works by taking one element at a time and placing it in its correct position within the already sorted part of the list.

The algorithm assumes the first element is sorted, then picks the next element (called the key) and compares it with the elements before it. If any element is larger than the key, it shifts that element one position to the right.

This process continues until the key is placed in the correct position. The same steps repeat for all elements until the entire list becomes sorted. It is an in-place, stable, and comparison-based sorting algorithm that works best for small or nearly sorted datasets.

How Insertion sort works?

1. Start from the second element
   • The first element is already considered sorted because a single element is always in order by itself.
   • So, the algorithm starts checking from the second element in the list.
2. Pick the current element (called “key”)
   • This element will be compared with the elements before it (the already sorted part).
   • The goal is to find the right position for this “key”.
3. Compare with previous elements
   • The algorithm checks the elements to the left of the key (in the sorted part) one by one.
   • If an element is greater than the key, it gets shifted one position to the right to make space.
4. Find the correct position
   • This comparison and shifting continue until the algorithm finds an element smaller than (or equal to) the key, or it reaches the beginning of the list.
   • Now, it knows exactly where the key should be placed.
5. Insert the key in its position
   • The key is placed in its correct spot in the sorted part of the list.
   • Now the sorted part has one more element.
6. Move to the next element
   • The algorithm now picks the next unsorted element and repeats the same process — comparing, shifting, and inserting.
7. Repeat until all elements are sorted
   • The process continues until there are no unsorted elements left.
   • By the end, all elements are in the correct order.

Example of Insertion Sort

Initially

• Array = [25, 1, 9, 5, 2]
• The first element 25 is considered sorted because a single element is always sorted by itself.

First Pass:

• The next element is 1.
• Compare 1 with 25.
• Since 1 < 25, we move 25 one position to the right.
• Place 1 before 25.
• Array becomes: [1, 25, 9, 5, 2]
  At the end of this pass, the first two elements (1 and 25) are sorted.

Second Pass:

• The next element to insert is 9.
• Compare 9 with 25. Since 9 < 25, move 25 one step right.
• Compare 9 with 1. Since 9 > 1, place 9 after 1.
• Array becomes: [1, 9, 25, 5, 2]
  Now, the first three elements (1, 9, 25) are sorted.

Third Pass:

• The next element to insert is 5.
• Compare 5 with 25. Since 5 < 25, move 25 one step right.
• Compare 5 with 9. Since 5 < 9, move 9 one step right.
• Compare 5 with 1. Since 5 > 1, insert 5 after 1.
• Array becomes: [1, 5, 9, 25, 2]
  Now, the first four elements (1, 5, 9, 25) are sorted.

Fourth Pass:

• The next element to insert is 2.
• Compare 2 with 25. Since 2 < 25, move 25 right.
• Compare 2 with 9. Since 2 < 9, move 9 right.
• Compare 2 with 5. Since 2 < 5, move 5 right.
• Compare 2 with 1. Since 2 > 1, insert 2 after 1.
• Array becomes: [1, 2, 5, 9, 25]

Final Result:

• All elements are now in sorted order — [1, 2, 5, 9, 25].

Pseudocode of Insertion Sort

InsertionSort(A):
    for i = 1 to length(A) - 1 do
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key do
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

C++ Program

#include <iostream>
using namespace std;

// Function to perform Insertion Sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];     // Element to be placed correctly
        int j = i - 1;        // Start comparing with previous elements

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

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

int main() {
    int arr[] = {25, 1, 9, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original Array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

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

    cout << "Sorted Array:   ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output

Original Array: 25 1 9 5 2
Sorted Array:   1 2 5 9 25

Explanation

The above C++ program demonstrates the working of the Insertion Sort algorithm. It begins by defining a function named insertionSort() that takes an array and its size as input. Inside this function, a for loop runs from the second element (i = 1) to the last element of the array. For each iteration, the current element is stored in a variable called key, which represents the element that needs to be placed in the correct sorted position. The variable j is initialized to i - 1 to compare the key with previous elements.

A while loop then checks if the current element (arr[j]) is greater than the key. If true, it shifts that element one position to the right (arr[j + 1] = arr[j]) and decrements j to continue checking previous elements. Once the correct position for the key is found, it is placed there using arr[j + 1] = key.

In the main() function, the program first initializes an array arr[] = {25, 1, 9, 5, 2} and calculates its size using sizeof(arr) / sizeof(arr[0]). It then displays the original array using a for loop. The insertionSort() function is called to sort the array, and finally, another for loop prints the sorted array in ascending order. The output of this program shows that the array has been successfully sorted from {25, 1, 9, 5, 2} to {1, 2, 5, 9, 25}.

Time Complexity Analysis

• Best-case time complexity: Best case can be considered when the input array is already sorted. It means the algorithm will only perform the comparisons but there will be no element shifting. In this case, the time complexity is Θ(n), where n is the number of elements in the array.
• Worst-case time complexity: The worst case will be, suppose the given array is in reverse order. In this condition, each element of the array will be compared and shifted to its correct position. The worst-case time complexity is O(n²)
• Average-case time complexity: O(n) average case, Insertion Sort performs Θ(n^2) comparisons and shifts.

Insertion Sort is an efficient algorithm to sort the small input sizes array. It is also a good option for partially sorted arrays.

Following properties of Insertion sort are:

• In-place sorting: Insertion Sort perform sorting of the elements by modifying the elements in-place without taking additional memory.
• Stable sorting: The algorithm maintains the relative order of elements with equal values, making it a stable sorting algorithm.
• Adaptive sorting: If the input array is already partially sorted, Insertion Sort can take advantage of this and perform fewer comparisons and shifts.

However, Insertion Sort is not suitable for large input sizes. It is because of its quadratic time complexity. It becomes inefficient if we compare it with more advanced sorting algorithms like Quick Sort or Merge Sort. These advanced sorting algorithms have better average-case and worst-case time complexities.

Overall, Insertion Sort is a simple and easy-to-implement sorting algorithm. But It is more suitable for small-size arrays and partially sorted arrays.

Advantages of Insertion Sort

1. Simple and Easy to Understand:
   Insertion sort is one of the simplest sorting algorithms. Its logic is straightforward, making it easy for beginners to learn and implement.
2. Efficient for Small Data Sets:
   It works efficiently when the number of elements is small. The overhead of comparisons and shifts is minimal for smaller datasets.
3. Best Choice for Nearly Sorted Data:
   If the data is already mostly sorted, insertion sort performs very fast because it just makes a few comparisons and shifts, giving a time complexity close to O(n).
4. In-Place Sorting Algorithm:
   It does not require any extra memory or temporary arrays. It sorts the data within the same array, so the space complexity is O(1).
5. Stable Sorting Algorithm:
   Insertion sort maintains the relative order of equal elements, which is important when sorting records that have multiple fields (like sorting by name while preserving order by date).
6. Adaptive in Nature:
   It automatically reduces the number of operations when the array is partially sorted, making it more efficient in such cases.
7. Online Sorting Capability:
   Insertion sort can sort a list as it receives new elements. This means it can be used for data that comes in streams (one element at a time).
8. Useful as a Subroutine:
   Insertion sort is often used inside more complex algorithms like Hybrid Sort (e.g., Tim Sort or Shell Sort) for small portions of data because of its simplicity and speed on small ranges.

Disadvantages of Insertion Sort

1. Inefficient for Large Data Sets:
   Insertion Sort becomes very slow when the number of elements increases. Its average and worst-case time complexity is O(n²), which makes it unsuitable for large datasets.
2. Too Many Comparisons and Shifts:
   For every element, the algorithm may need to compare and shift many other elements to find the correct position, which increases the total number of operations.
3. Performance Depends on Input Order:
   The algorithm performs very well when the data is nearly sorted but very poorly when the data is completely unsorted or sorted in reverse order.
4. Not Suitable for Complex Applications:
   Since it is slow and simple, Insertion Sort is rarely used in real-world large-scale applications where faster algorithms like Merge Sort, Quick Sort, or Heap Sort are preferred.
5. Sequential Processing Only:
   Insertion sort cannot be easily parallelized because each step depends on the result of the previous step, which limits its performance on modern multi-core processors.
6. More Time for Shifting Elements:
   Every time a smaller element is inserted into the correct position, all larger elements need to be moved one step ahead, which increases execution time for big arrays.