Sorting algorithms compared
Insertion sort, merge sort, quicksort and counting sort compared by speed, memory and stability.
| Algorithm | Average | Worst | Stable | Notes |
|---|---|---|---|---|
| Insertion sort | O(n^2) | O(n^2) | yes | fast for small or nearly sorted data |
| Merge sort | O(n log n) | O(n log n) | yes | needs O(n) extra memory |
| Quicksort | O(n log n) | O(n^2) | no | fast in practice, in place |
| Counting sort | O(n + k) | O(n + k) | yes | small integer keys only |
Stable means equal elements keep their original order, which matters when sorting by one field after another. In real code, use std::sort (an introsort hybrid, never O(n^2)) or std::stable_sort.
Example
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Player {
std::string name;
int score;
};
int main() {
std::vector<Player> ps{{"Ada", 90}, {"Bob", 75}, {"Cy", 90}, {"Di", 75}};
std::stable_sort(ps.begin(), ps.end(), [](const Player &a, const Player &b) { return a.score > b.score; });
for (const auto &p : ps) std::cout << p.name << " ";
std::cout << "\n";
return 0;
}
Output:
Ada Cy Bob Di
Watch it run: Insertion sort, step by step