Home | Projects | Notes > Data Structures & Algorithms > Insertion Sort: T = O(n²) , S = O(1)

Insertion Sort: T = O(n²) , S = O(1)

Insertion Sort

• A simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input list and, in each iteration, compares the current element with the elements to its left and inserts it into the correct position within the already sorted portion of the array. This process is repeated until the entire array is sorted.

• Insertion sort has a time complexity of O(n²) but performs better on partially sorted or small lists compared to other quadratic time complexity algorithms.

• Insertion sort has a space complexity of O(1). It sorts the array in place, that is, It does not create additional copies of the array.

Algorithm

1. Input: An array of elements to be sorted.

2. Loop: Start a loop that iterates from the second element to the last element of the array.

3. Current Element: For the current iteration, store the value of the element to be inserted into the sorted portion.

4. Inner Loop: Within the loop, iterate from the current element's position back to the beginning of the array (or until a smaller element is found).

5. Shift and Insert: While iterating in the inner loop, if the current element is smaller than the element being compared, shift the compared element to the right to make space for the current element.

6. Insert Current Element: Once a suitable position is found in the inner loop, insert the current element into that position.

7. Repeat: Continue this process for each element in the array until the entire array is sorted.

Pseudo-code

xxxxxxxxxx
9
1
InsertionSort(arr):
2
    n = length(arr)
3
    for i from 1 to n-1:
4
        current = arr[i]
5
        j = i-1
6
        while j > -1 and arr[j] > current:
7
            arr[j+1] = arr[j]
8
            j = j-1
9
        arr[j+1] = current

L6: The order in which you write the two condition statements of the while loop is very important. Switching the order will cause a run-time error for referencing arr[-1].

Code

xxxxxxxxxx
35
1
#include <iostream>
2

3
using namespace std;
4

5
void insertionSort(int arr[], int size)
6
{
7
    for (int i = 1; i < size; i++)  // Loop: 2nd element - last element
8
    {
9
        int curr = arr[i];          // curr: element to find correct spot in this pass
10
        int j = i - 1;              
11
        
12
        while (j > -1 && arr[j] > curr)
13
        {
14
            arr[j + 1] = arr[j];    // Move an array element to the right
15
            j = j - 1;
16
        }
17
        
18
        arr[j + 1] = curr;  // Insert the current element into the correct spot
19
    }
20
}
21

22
int main(void)
23
{
24
    int arr[] = {6, 4, 2, 1, 5, 3};
25
    int size = sizeof(arr) / sizeof(arr[0]);
26
    
27
    insertionSort(arr, size);
28
    
29
    for (auto val : arr)
30
        cout << val << " ";
31
    
32
    cout << endl;
33
    
34
    return 0;
35
}

xxxxxxxxxx
1
1
1 2 3 4 5 6