代码

#include <algorithm>

using u32 = unsigned int;

void m_sort(u32 *l, u32 *r, u32 k = 128) {
    if (k == 128) {
        --r;
        k = 0;
        for (u32 *t = l; t <= r; ++t)
            k = max(k, std::__lg(*t));
    }
    if (l >= r) return;
    if (l == r - 1) {
        if (*l > *r) std::swap(*l, *r);
        return;
    }
    auto p = l, q = r;
    while (p <= q) {
        if ((*p >> k) & 1) {
            while (p < q && (*q >> k) & 1)
                --q;
            if (p == q) {
                if (k == 0) return;
                m_sort(l, p - 1, k - 1);
                m_sort(p, r, k - 1);
                return;
            }
            std::swap(*p, *q);
        }
        ++p;
    }
    if (k == 0) return;
    m_sort(l, q, k - 1);
    m_sort(q + 1, r, k - 1);
}

void sort(unsigned *a, int n) {
	m_sort(a, a + n);
}

评测结果