代码

#include <algorithm>

#include <stdint.h>

static void insertion_sort(uint32_t *a, int l, int r) {
    for (int i = l + 1; i < r; i++) {
        uint32_t key = a[i];
        int j = i - 1;
        while (j >= l && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

static void msd_radix_sort(uint32_t *a, int l, int r, int bit) {
    if (r - l <= 32) {
        insertion_sort(a, l, r);
        return;
    }
    if (bit < 0) return;

    int i = l, j = r - 1;
    while (i <= j) {
        while (i <= j && ((a[i] >> bit) & 1U) == 0) i++;
        while (i <= j && ((a[j] >> bit) & 1U) == 1) j--;
        if (i < j) {
            uint32_t tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }
    msd_radix_sort(a, l, i, bit - 1);
    msd_radix_sort(a, i, r, bit - 1);
}

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    msd_radix_sort((uint32_t*)a, 0, n, 31);
}

评测结果