Insertion Sort Algorithm

1. Algorithm Explanation

Insertion Sort builds the sorted array one element at a time. It maintains a “sorted” subarray on the left and iteratively inserts the next element from the unsorted portion into its correct position in the sorted portion.

1. Start with the second element (index 1). Assume the first element is a sorted subarray of size 1.
2. Save the current element (key).
3. Compare key with elements in the sorted subarray (from rightmost to leftmost).
4. Shift elements that are greater than key one position to the right.
5. Insert key into its correct position.
6. Repeat for all elements until the entire array is sorted.

2. Time and Memory Complexity

• Worst-case time: O(n²) — occurs when the input is in reverse order; each insertion requires shifting all previous elements.
• Average-case time: O(n²).
• Best-case time: O(n) — occurs when the input is already sorted; only one comparison per element.
• Memory (auxiliary): O(1) — in-place sorting, uses only a constant amount of extra memory.

3. Easy Problems

3.1. Problem 1: Insert Element Into Sorted Array

Given a sorted array and a value x, insert x into the array so that it remains sorted.

// C++ solution
#include <iostream>
#include <vector>
using namespace std;

void insertIntoSorted(vector& arr, int x) {
  arr.push_back(x);  // make space
  int i = arr.size() - 2;
  while (i >= 0 && arr[i] > x) {
    arr[i + 1] = arr[i];
    i--;
  }
  arr[i + 1] = x;
}

int main() {
  vector arr = {1, 3, 5, 7};
  int x = 4;
  insertIntoSorted(arr, x);
  for (int v : arr) cout << v << " ";
  return 0;
}
  

3.2. Problem 2: Sort Small Array

Given an array of at most 100 elements, sort it using insertion sort.

// C++ solution
#include <iostream>
#include <vector>
using namespace std;

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

int main() {
  vector arr = {9, 2, 7, 3, 6};
  insertionSort(arr);
  for (int v : arr) cout << v << " ";
  return 0;
}
  

4. Intermediate Problems

4.1. Problem 3: Count Inversions for Nearly Sorted Array

Given an array where each element is at most k positions away from its sorted position, count the number of inversions by using insertion sort to accumulate shifts.

// C++ solution
#include <iostream>
#include <vector>
using namespace std;

// Returns number of shifts ≡ inversions for a nearly sorted array.
long long countInversions(vector& arr) {
  int n = arr.size();
  long long inv = 0;
  for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
      inv++;
    }
    arr[j + 1] = key;
  }
  return inv;
}

int main() {
  vector arr = {2, 1, 3, 5, 4};
  cout << "Inversions: " << countInversions(arr);
  return 0;
}
  

4.2. Problem 4: Sort a Linked List of Small Size

Given a singly linked list with at most 1000 nodes, sort it in-place using insertion sort on the list nodes.

// C++ solution
#include <iostream>
using namespace std;

struct Node {
  int val;
  Node* next;
  Node(int v): val(v), next(nullptr) {}
};

Node* insertionSortList(Node* head) {
  Node dummy(0);
  Node* tail = &dummy;
  Node* cur = head;
  while (cur) {
    Node* next = cur->next;
    // find insertion position
    Node* p = &dummy;
    while (p->next && p->next->val < cur->val)
      p = p->next;
    // insert cur between p and p->next
    cur->next = p->next;
    p->next = cur;
    cur = next;
  }
  return dummy.next;
}

int main() {
  Node* head = new Node(4);
  head->next = new Node(2);
  head->next->next = new Node(5);
  head->next->next->next = new Node(1);
  Node* sorted = insertionSortList(head);
  while (sorted) {
    cout << sorted->val << " ";
    sorted = sorted->next;
  }
  return 0;
}
  

5. Hard Problem

5.1. Problem 5: Online Median Maintenance for Small Streams

Maintain a running median of a stream of integers where the stream length is at most 10⁴. Insert each new element into a sorted structure via insertion sort logic and compute the median in O(n²) worst-case, acceptable for small n.

// C++ solution
#include <iostream>
#include <vector>
using namespace std;

class RunningMedian {
  vector data;
public:
  void insert(int x) {
    // insertion sort step
    data.push_back(x);
    int i = data.size() - 2;
    while (i >= 0 && data[i] > x) {
      data[i + 1] = data[i];
      i--;
    }
    data[i + 1] = x;
  }
  double getMedian() {
    int n = data.size();
    if (n % 2)
      return data[n/2];
    else
      return (data[n/2 - 1] + data[n/2]) / 2.0;
  }
};

int main() {
  RunningMedian rm;
  vector stream = {5, 15, 1, 3};
  for (int x : stream) {
    rm.insert(x);
    cout << "Median after " << x << ": " << rm.getMedian() << "\n";
  }
  return 0;
}