insertion sort
Insertion sort is exactly how most people sort a hand of playing cards: keep a tidy sorted run on the left, then pick up the next card and slide it leftward past any cards bigger than it, dropping it into its right spot. Repeat until the unsorted pile is gone. At every moment the left part is fully sorted; you just keep growing it one card at a time.
Mechanically, you walk through the array from left to right. For each new element you compare it with the sorted elements behind it and shift those that are too big one slot to the right, opening a gap to drop the new element into. The shifting is what does the work, and the amount of shifting depends entirely on how out of order the data already is.
On nearly-sorted data this is wonderful: each element barely moves, so the cost approaches O(n) — in the best case (already sorted) it's exactly O(n). But on average, and in the worst case (reverse-sorted), elements travel far and the cost is O(n^2). It sorts in place with O(1) extra space and is stable (equal keys keep their original order). For small or almost-sorted inputs it's hard to beat, which is why real-world sort libraries fall back to it for tiny sub-arrays.
void insertionSort(std::vector<int>& a) {
for (int i = 1; i < (int)a.size(); ++i) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger ones right
a[j + 1] = a[j];
--j;
}
a[j + 1] = key; // drop key into the gap
}
}key is held aside while larger elements shift right to open its slot.
Stable + in-place + adaptive (fast on nearly-sorted data) is a rare trio. That's why Timsort and many std::sort implementations switch to insertion sort once a sub-array shrinks below a small threshold.