Insertion Sort

Intuition

This works as follow,

• Consider you have a sorted array and you want to insert a element
• you will scan through the end of the sorted array and keep on shifting elements to right till the right position of element you want to insert is not found.

#include <bits/stdc++.h>
using namespace std;

void insertion_sort(vector<int> &a) {
    int key = 0;
    for (int i = 1; i < a.size(); i++) {
        key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[++j] = key;
    }
}

int main() {
    vector<int> a = {1, 4, 2, 5, 5, 6, 3, 3, 4};
    insertion_sort(a);
    for (auto i : a) cout << i << " ";
    return 0;
}

Analysis

• Time complexity
  • Best: \(O(n)\), if the array is sorted
  • Average: \(O(n^2)\)
  • Worst: \(O(n^2)\)
• Space complexity - \(O(1)\)