</>EmbeddedInterview

Implement merge sort.

Medium"Coding: Sorting & Array Problems"
#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.