C++ sorting: insertion sort, merge sort, and std::stable_sort

Before you start

C++ vectors, recursion, and lambdas.

Write two sorts by hand and sort records with a comparator, keeping equal items in order.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Insertion sort builds a sorted prefix by inserting each element in the right place. It is O(n²) in the worst case but very fast for short or nearly sorted data. Merge sort splits the data, sorts both halves recursively, and merges them. It takes O(n log n) time in every case, using O(n) extra space, and it is stable if equal elements are taken from the left half first.

A sort is stable if equal elements keep their original order. std::sort is not guaranteed to be stable, while std::stable_sort is. Stability matters when sorting records by one key after another. Here the students are already ordered by name, and stable_sort by grade keeps alphabetical order inside each grade.

Code example

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

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

std::vector<int> merge_sort(const std::vector<int>& a) {
  if (a.size() <= 1) {
    return a;
  }
  std::size_t mid = a.size() / 2;
  std::vector<int> left = merge_sort(std::vector<int>(a.begin(), a.begin() + mid));
  std::vector<int> right = merge_sort(std::vector<int>(a.begin() + mid, a.end()));
  std::vector<int> merged;
  std::size_t i = 0, j = 0;
  while (i < left.size() && j < right.size()) {
    merged.push_back(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  while (i < left.size()) merged.push_back(left[i++]);
  while (j < right.size()) merged.push_back(right[j++]);
  return merged;
}

struct Student {
  std::string name;
  int grade;
};

int main() {
  std::vector<int> data = {5, 2, 9, 1, 5, 6};
  std::vector<int> copy = data;
  insertion_sort(copy);
  for (int x : copy) std::cout << x << " ";
  std::cout << "\n";
  for (int x : merge_sort(data)) std::cout << x << " ";
  std::cout << "\n";

  std::vector<Student> students = {{"Ada", 90}, {"Bo", 85}, {"Cy", 90}, {"Di", 85}};
  std::stable_sort(students.begin(), students.end(),
                   [](const Student& a, const Student& b) { return a.grade > b.grade; });
  for (const Student& s : students) std::cout << s.name << ":" << s.grade << " ";
  std::cout << "\n";
}

Output

1 2 5 5 6 9
1 2 5 5 6 9
Ada:90 Cy:90 Bo:85 Di:85

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <algorithm>

2#include <iostream>

3#include <string>

4#include <vector>

6void insertion_sort(std::vector<int>& a) {

7 for (std::size_t i = 1; i < a.size(); ++i) {

8 int key = a[i];

9 std::size_t j = i;

10 while (j > 0 && a[j - 1] > key) {

11 a[j] = a[j - 1];

12 --j;

13 }

14 a[j] = key;

15 }

16}

18std::vector<int> merge_sort(const std::vector<int>& a) {

19 if (a.size() <= 1) {

20 return a;

21 }

22 std::size_t mid = a.size() / 2;

23 std::vector<int> left = merge_sort(std::vector<int>(a.begin(), a.begin() + mid));

24 std::vector<int> right = merge_sort(std::vector<int>(a.begin() + mid, a.end()));

25 std::vector<int> merged;

26 std::size_t i = 0, j = 0;

27 while (i < left.size() && j < right.size()) {

28 merged.push_back(left[i] <= right[j] ? left[i++] : right[j++]);

29 }

30 while (i < left.size()) merged.push_back(left[i++]);

31 while (j < right.size()) merged.push_back(right[j++]);

32 return merged;

33}

35struct Student {

36 std::string name;

37 int grade;

38};

40int main() {

41 std::vector<int> data = {5, 2, 9, 1, 5, 6};

42 std::vector<int> copy = data;

43 insertion_sort(copy);

44 for (int x : copy) std::cout << x << " ";

45 std::cout << "\n";

46 for (int x : merge_sort(data)) std::cout << x << " ";

47 std::cout << "\n";

49 std::vector<Student> students = {{"Ada", 90}, {"Bo", 85}, {"Cy", 90}, {"Di", 85}};

50 std::stable_sort(students.begin(), students.end(),

51 [](const Student& a, const Student& b) { return a.grade > b.grade; });

52 for (const Student& s : students) std::cout << s.name << ":" << s.grade << " ";

53 std::cout << "\n";

54}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Shift larger elements right until the key fits.	`—`	—
Take the smaller front element. Taking from the left on a tie keeps the sort stable.	`—`	—
Sort a copy so that the original data can be reused.	`—`	—
Sort by grade, highest first. Equal grades keep their previous alphabetical order.	`—`	—
Ada and Cy (90) come first in their original order, then Bo and Di (85).	`—`	1 2 5 5 6 9 1 2 5 5 6 9 Ada:90 Cy:90 Bo:85 Di:85

Behind the scenes

How C++ processes this code

The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.

Cost and common mistakes

Insertion sort O(n²) worst case. Merge sort and stable_sort O(n log n).

A comparator must be a strict weak ordering. Using >= instead of > in the lambda can crash std::sort.
Output lines here end with a trailing space after the last item, which is easy to overlook in tests.
For small ranges the library's sorts already switch to insertion sort internally.

Try it yourself

Which of std::sort and std::stable_sort would you choose to sort by two keys in two passes?

Reveal answer and reasoning

std::stable_sort, because the second pass must not undo the order created by the first.