Sorting overview

Lesson

Sorting transforms data into ascending (or descending) order. Common algorithms:

• Bubble / insertion sort: O(n²) — fine for small arrays.
• Mergesort: O(n log n), stable, needs O(n) extra space.
• Quicksort: O(n log n) average, O(n²) worst case, in-place.
• Heapsort: O(n log n) guaranteed, in-place, not stable.

In real code: use qsort from <stdlib.h> — battle-tested and fast.

Code examples

#include <stdlib.h>
int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
qsort(arr, n, sizeof(int), cmp);

Common mistakes

• Comparator that subtracts ints: overflows for extreme values. Use comparison operators returning -1/0/1 instead.