Implement merge sort.
#include <stddef.h>
#include <string.h>
static void merge(int *a, int *tmp, size_t lo, size_t mid, size_t hi) /* [lo,mid) + [mid,hi) */
{
size_t i = lo, j = mid, k = lo;
while (i < mid && j < hi) tmp[k++] = (a[j] < a[i]) ? a[j++] : a[i++]; /* <= keeps it stable */
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
memcpy(a + lo, tmp + lo, (hi - lo) * sizeof *a);
}
/* bottom-up: no recursion, needs an n-element scratch buffer */
void merge_sort(int *a, int *tmp, size_t n)
{
for (size_t width = 1; width < n; width *= 2)
for (size_t lo = 0; lo < n - width; lo += 2 * width) {
size_t mid = lo + width;
size_t hi = (mid + width < n) ? mid + width : n;
merge(a, tmp, lo, mid, hi);
}
}
Points: O(n log n) in all cases (predictable timing), stable, but needs O(n) extra memory for arrays. The bottom-up form avoids recursion (good for small stacks). For linked lists, merge sort needs no extra memory, which makes it the standard way to sort lists.