Compare adjacent items, swap if out of order; after each pass the largest bubbles to the end. Comparisons n(n-1)/2 -> O(n^2); best O(n). Stable, in-place, O(1) space.
Find the minimum, swap into the first unsorted slot; repeat (one swap per pass). Must always scan for the minimum, so O(n^2) in all cases; in-place, not stable.
Insert each element into its place in a growing sorted region. Best O(n), average/worst O(n^2), O(1) space. Advantages: simple, good on small/almost-sorted data, stable, in-place, online.
Split into halves, sort recursively, merge with three pointers. T(n)=2T(n/2)+n -> O(n log n) all cases; space O(n). Stable, not in-place. Inversion counting, external sorting.
Pick a pivot, partition (left <= pivot < right), recurse. Worst (sorted input) O(n^2); average/best O(n log n). Not stable, in-place.
Max-heap: parent >= children; PARENT=i/2, LEFT=2i, RIGHT=2i+1. MAX-HEAPIFY O(log n); BUILD-MAX-HEAP O(n); HEAP-SORT swaps root/last and re-heapifies -> O(n log n). In-place, not stable.
Counting: integers 1..k; arrays A, B, C; stable; Theta(n+k). Bucket: uniform [0,1); n buckets, sort each; average linear. Radix: stable sort digit by digit LSD to MSD; Theta(d(n+k)).