C++UCS301
Sorting AlgorithmsC++17

Insertion Sort

Insertion sort grows a sorted prefix by shifting larger values and inserting each new element into its correct position.

Open this in the visual lab

What to understand

  • Sorted-prefix invariant
  • Shifting instead of swapping
  • Adaptive behaviour
  • Online sorting

Remember this

  1. 1Excellent for small or nearly sorted input
  2. 2Stable and in-place
  3. 3Used inside many hybrid sorts

Detailed notes

Insertion sort maintains a sorted prefix. The next key is saved, larger prefix elements shift right, and the key enters the created gap. Shifting avoids the extra writes of repeated swaps.

Its work equals the number of inversions up to linear overhead, so nearly sorted input approaches O(n). It is online and is commonly used for small base cases inside hybrid sorts.

How it works

  1. 1Save the current key before shifting.
  2. 2Scan left while preceding values are greater.
  3. 3Shift each greater value one position right.
  4. 4Place the key in the final gap.

Worked trace

Insert key 3

Sorted prefix [1,4,6], key=3
  1. 1Save key 3 before overwriting its slot.
  2. 26 > 3, so shift 6 right.
  3. 34 > 3, so shift 4 right.
  4. 41 ≤ 3, so place 3 after 1.
Result: [1,3,4,6]

Where it is used

  • Small or nearly sorted arrays
  • Online maintenance of a sorted prefix
  • Base cases in TimSort and introspective algorithms

Common mistakes

  • Overwriting the key before saving it
  • Using >= and unintentionally destroying stability
  • Accessing index −1 before checking the bound

Complexity analysis

OperationBestAverageWorstExtra space
SortO(n)O(n²)O(n²)O(1)

C++ implementation

C++17 reference
main.cpp

Insertion sort

Shift the sorted prefix to open one position for the current key.

void insertionSort(vector<int>& values) {
    for (int i = 1; i < static_cast<int>(values.size()); ++i) {
        int key = values[i];
        int j = i - 1;
        while (j >= 0 && values[j] > key) {
            values[j + 1] = values[j];
            --j;
        }
        values[j + 1] = key;
    }
}
11 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.