C++ sorting: insertion sort, merge sort, and std::stable_sort
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.
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";
}