代码

#ifndef QNQ_ALGORITHM_OLD_H
#define QNQ_ALGORITHM_OLD_H
#include <cstddef>
#include <type_traits>
#include <cmath>
#include <cstring>
#include <new>
#include <iterator>
#include <cstdint>

namespace qnq_old {
#if defined(__GNUC__) || defined(__clang__)
    #define QNQ_LIKELY(x)      __builtin_expect(!!(x), 1)
    #define QNQ_UNLIKELY(x)    __builtin_expect(!!(x), 0)
    #define QNQ_PREFETCH(p)    __builtin_prefetch(p)
    #define QNQ_FORCE_INLINE   __attribute__((always_inline)) inline
#else
    #define QNQ_LIKELY(x)      (x)
    #define QNQ_UNLIKELY(x)    (x)
    #define QNQ_PREFETCH(p)    ((void)0)
    #define QNQ_FORCE_INLINE   inline
#endif

static constexpr size_t INSERTION_SORT_THRESHOLD = 128;
static constexpr size_t COUNTING_SORT_RANGE_LIMIT = 65000;
static constexpr size_t PARTIAL_ORDER_MIN_SIZE   = 128;
static constexpr size_t SAMPLE_SIZE              = 128;
static constexpr size_t MAX_BUCKETS              = 4096;
static constexpr size_t PREFETCH_DIST            = 32;
static constexpr double MAX_BUCKETS_F            = static_cast<double>(MAX_BUCKETS);

template<typename T>
struct default_less {
    QNQ_FORCE_INLINE bool operator()(const T& a, const T& b) const { return a < b; }
};

template<typename Iter,
         typename Compare = default_less<typename std::iterator_traits<Iter>::value_type>>
inline void sort(Iter begin, Iter end, Compare cmp = Compare());

namespace detail {
    template<typename T>
    void destroy_range(T* p, size_t n, std::true_type) {
        // trivially destructible: do nothing
    }
    template<typename T>
    void destroy_range(T* p, size_t n, std::false_type) {
        for (size_t i = 0; i < n; ++i) {
            p[i].~T();
        }
    }
    template<typename T>
    void destroy_range(T* p, ptrdiff_t n, std::true_type) {}
    template<typename T>
    void destroy_range(T* p, ptrdiff_t n, std::false_type) {
        for (ptrdiff_t i = 0; i < n; ++i) {
            p[i].~T();
        }
    }
}

template<typename T>
class temp_buffer {
    T* data_;
    size_t capacity_;
public:
    temp_buffer() : data_(nullptr), capacity_(0) {}
    ~temp_buffer() {
        if (data_) {
            using IsTrivial = typename std::is_trivially_destructible<T>::type;
            detail::destroy_range(data_, capacity_, IsTrivial{});
            operator delete(data_);
        }
    }
    void resize(size_t n) {
        if (QNQ_LIKELY(n <= capacity_)) return;
        if (data_) {
            using IsTrivial = typename std::is_trivially_destructible<T>::type;
            detail::destroy_range(data_, capacity_, IsTrivial{});
            operator delete(data_);
        }
        data_ = static_cast<T*>(operator new(n * sizeof(T)));
        capacity_ = n;
    }
    T* data() { return data_; }
    temp_buffer(const temp_buffer&) = delete;
    temp_buffer& operator=(const temp_buffer&) = delete;
};

template<typename Iter>
inline void reverse_iter(Iter begin, Iter end) {
    if (begin == end) return;
    --end;
    while (begin < end) {
        typename std::iterator_traits<Iter>::value_type tmp = *begin;
        *begin = *end;
        *end = tmp;
        ++begin;
        --end;
    }
}

template<typename Iter, typename Compare>
void stable_merge(Iter begin, Iter mid, Iter end, Compare cmp) {
    using V = typename std::iterator_traits<Iter>::value_type;
    ptrdiff_t n1 = mid - begin, n2 = end - mid;
    if (n1 == 0 || n2 == 0) return;
    static temp_buffer<V> buf;
    buf.resize(static_cast<size_t>(n1));
    V* tmp = buf.data();
    for (ptrdiff_t i = 0; i < n1; ++i) {
        new (tmp + i) V(begin[i]);
    }
    ptrdiff_t i = 0, j = 0, k = 0;
    while (i < n1 && j < n2) {
        if (cmp(mid[j], tmp[i])) begin[k++] = mid[j++];
        else                     begin[k++] = tmp[i++];
    }
    while (i < n1) begin[k++] = tmp[i++];
    while (j < n2) begin[k++] = mid[j++];

    using IsTrivial = typename std::is_trivially_destructible<V>::type;
    detail::destroy_range(tmp, n1, IsTrivial{});
}

template<typename Iter, typename Compare>
inline void insertion_sort(Iter begin, Iter end, Compare cmp) {
    if (begin == end) return;
    for (Iter i = begin + 1; i != end; ++i) {
        auto tmp = *i;
        Iter j = i;
        while (j != begin && cmp(tmp, *(j - 1))) {
            *j = *(j - 1);
            --j;
        }
        *j = tmp;
    }
}

namespace detail {
    template<typename V, typename Iter, typename Compare>
    bool counting_sort_impl(Iter begin, Iter end, Compare cmp, std::true_type /* integral */) {
        ptrdiff_t n = end - begin;
        if (n <= 1) return true;
        V min_val = *begin, max_val = *begin;
        for (Iter it = begin + 1; it != end; ++it) {
            if (cmp(*it, min_val)) min_val = *it;
            if (cmp(max_val, *it)) max_val = *it;
        }
        using wide = typename std::conditional<sizeof(V) < 4, int64_t, V>::type;
        wide r = static_cast<wide>(max_val) - static_cast<wide>(min_val);
        if (r < 0 || static_cast<size_t>(r) > COUNTING_SORT_RANGE_LIMIT) return false;
        size_t range = static_cast<size_t>(r) + 1;
        uint32_t* counts = static_cast<uint32_t*>(__builtin_alloca(range * sizeof(uint32_t)));
        std::memset(counts, 0, range * sizeof(uint32_t));
        for (Iter it = begin; it != end; ++it) {
            ++counts[static_cast<size_t>(static_cast<wide>(*it) - static_cast<wide>(min_val))];
        }
        uint32_t total = 0;
        for (size_t i = 0; i < range; ++i) {
            uint32_t c = counts[i];
            counts[i] = total;
            total += c;
        }
        static temp_buffer<V> buf;
        buf.resize(static_cast<size_t>(n));
        V* tmp = buf.data();
        for (Iter it = begin; it != end; ++it) {
            size_t idx = static_cast<size_t>(static_cast<wide>(*it) - static_cast<wide>(min_val));
            new (tmp + counts[idx]++) V(*it);
        }
        for (ptrdiff_t i = 0; i < n; ++i) begin[i] = tmp[i];
        using IsTrivial = typename std::is_trivially_destructible<V>::type;
        detail::destroy_range(tmp, n, IsTrivial{});
        return true;
    }
    template<typename V, typename Iter, typename Compare>
    bool counting_sort_impl(Iter, Iter, Compare, std::false_type) {
        return false;
    }
}

template<typename Iter, typename Compare>
inline bool counting_sort_if_possible(Iter begin, Iter end, Compare cmp) {
    using V = typename std::iterator_traits<Iter>::value_type;
    using IsInt = typename std::is_integral<V>::type;
    return detail::counting_sort_impl<V>(begin, end, cmp, IsInt{});
}

template<typename Iter, typename Compare>
inline bool handle_partial_ordered(Iter begin, Iter end, Compare cmp) {
    ptrdiff_t n = end - begin;
    if (n <= static_cast<ptrdiff_t>(PARTIAL_ORDER_MIN_SIZE)) return false;
    Iter prefix_end = begin;
    while (prefix_end + 1 != end && !cmp(*(prefix_end + 1), *prefix_end))
        ++prefix_end;
    ptrdiff_t prefix_len = prefix_end - begin + 1;
    Iter suffix_start = end - 1;
    while (suffix_start != begin && !cmp(*suffix_start, *(suffix_start - 1)))
        --suffix_start;
    ptrdiff_t suffix_len = end - suffix_start;
    if (prefix_len + suffix_len > n * 7 / 10) {
        Iter mid_begin = prefix_end + 1;
        Iter mid_end   = suffix_start;
        ptrdiff_t mid_len = mid_end - mid_begin;
        if (mid_len > 1) qnq_old::sort(mid_begin, mid_end, cmp);
        if (prefix_len > 0 && mid_len > 0)
            stable_merge(begin, prefix_end + 1, mid_end, cmp);
        if (prefix_len + mid_len > 0 && suffix_len > 0)
            stable_merge(begin, begin + prefix_len + mid_len, end, cmp);
        return true;
    }
    return false;
}

QNQ_FORCE_INLINE size_t compute_k(size_t n) {
    size_t k;
    if (n < 200000) {
        k = static_cast<size_t>(3.5 * std::sqrt(static_cast<double>(n)));
        if (k < 512)  k = 512;
        if (k > 2048) k = 2048;
    } else if (n < 2000000) {
        k = static_cast<size_t>(2.5 * std::sqrt(static_cast<double>(n)));
        if (k < 1024) k = 1024;
        if (k > 4096) k = 4096;
    } else {
        k = static_cast<size_t>(0.5 * std::sqrt(static_cast<double>(n)));
        if (k < 1024) k = 1024;
        if (k > 2048) k = 2048;
    }
    if (k > MAX_BUCKETS) k = MAX_BUCKETS;
    if (k > n) k = n;
    if (k < 2) k = 2;
    return k;
}

QNQ_FORCE_INLINE uint16_t int_bucket(uint64_t diff, uint64_t recip) {
    uint64_t prod = diff * recip;
    uint32_t idx = static_cast<uint32_t>(prod >> 32);
    return static_cast<uint16_t>(QNQ_LIKELY(idx < MAX_BUCKETS) ? idx : MAX_BUCKETS - 1);
}

template<typename F>
QNQ_FORCE_INLINE uint16_t float_bucket(F val, F min_val, double scale_f) {
    double norm = (static_cast<double>(val) - static_cast<double>(min_val)) * scale_f;
    size_t idx = static_cast<size_t>(norm);
    return static_cast<uint16_t>(QNQ_LIKELY(idx < MAX_BUCKETS) ? idx : MAX_BUCKETS - 1);
}

namespace detail {
    template<typename V, typename Iter, typename Compare>
    void zsort_rec_arith(Iter begin, Iter end, Compare cmp, std::true_type /* integral */) {
        ptrdiff_t n = end - begin;
        size_t m = static_cast<size_t>(n) < SAMPLE_SIZE ? static_cast<size_t>(n) : SAMPLE_SIZE;
        V sample[SAMPLE_SIZE];
        if (m == static_cast<size_t>(n)) {
            for (size_t i2 = 0; i2 < m; ++i2) sample[i2] = begin[i2];
        } else {
            size_t step = static_cast<size_t>(n) / m;
            for (size_t i2 = 0; i2 < m; ++i2) sample[i2] = begin[i2 * step];
        }
        insertion_sort(sample, sample + m, cmp);
        size_t k = compute_k(static_cast<size_t>(n));

        V min_val = *begin;
        V max_val = *begin;
        ptrdiff_t i = 1;
        for (; i + 4 <= n; i += 4) {
            V v0 = *(begin + i);
            V v1 = *(begin + i + 1);
            V v2 = *(begin + i + 2);
            V v3 = *(begin + i + 3);
            if (v0 < min_val) min_val = v0;
            if (v1 < min_val) min_val = v1;
            if (v2 < min_val) min_val = v2;
            if (v3 < min_val) min_val = v3;
            if (max_val < v0) max_val = v0;
            if (max_val < v1) max_val = v1;
            if (max_val < v2) max_val = v2;
            if (max_val < v3) max_val = v3;
        }
        for (; i < n; ++i) {
            V v = *(begin + i);
            if (v < min_val) min_val = v;
            if (max_val < v) max_val = v;
        }

        int64_t  base_int = static_cast<int64_t>(min_val);
        int64_t range = static_cast<int64_t>(max_val) - base_int;
        if (QNQ_UNLIKELY(range <= 0)) {
            insertion_sort(begin, end, cmp);
            return;
        }
        uint64_t recip = (static_cast<uint64_t>(MAX_BUCKETS) << 32) / static_cast<uint64_t>(range);
        if (QNQ_UNLIKELY(recip == 0)) recip = 1;

        uint16_t table[MAX_BUCKETS];
        {
            double mf = static_cast<double>(m);
            for (size_t i2 = 0; i2 < MAX_BUCKETS; ++i2) {
                double t = static_cast<double>(i2 + 1) / MAX_BUCKETS_F;
                size_t target = static_cast<size_t>(t * mf);
                if (target >= m) target = m - 1;
                size_t bucket = static_cast<size_t>(static_cast<double>(target) / mf * static_cast<double>(k));
                if (bucket >= k) bucket = k - 1;
                table[i2] = static_cast<uint16_t>(bucket);
            }
        }
        static temp_buffer<uint16_t> bucket_buf;
        bucket_buf.resize(static_cast<size_t>(n));
        uint16_t* bucket_cache = bucket_buf.data();
        uint32_t* hist = static_cast<uint32_t*>(__builtin_alloca(k * sizeof(uint32_t)));
        std::memset(hist, 0, k * sizeof(uint32_t));
        ptrdiff_t i2 = 0;
        const int64_t base = base_int;
        const uint64_t r = recip;
        for (; i2 + 4 <= n; i2 += 4) {
            QNQ_PREFETCH(&*(begin + i2 + PREFETCH_DIST));
            uint16_t b0 = table[int_bucket(static_cast<uint64_t>(static_cast<int64_t>(*(begin + i2))     - base), r)];
            uint16_t b1 = table[int_bucket(static_cast<uint64_t>(static_cast<int64_t>(*(begin + i2 + 1)) - base), r)];
            uint16_t b2 = table[int_bucket(static_cast<uint64_t>(static_cast<int64_t>(*(begin + i2 + 2)) - base), r)];
            uint16_t b3 = table[int_bucket(static_cast<uint64_t>(static_cast<int64_t>(*(begin + i2 + 3)) - base), r)];
            bucket_cache[i2]     = b0;
            bucket_cache[i2 + 1] = b1;
            bucket_cache[i2 + 2] = b2;
            bucket_cache[i2 + 3] = b3;
            ++hist[b0]; ++hist[b1]; ++hist[b2]; ++hist[b3];
        }
        for (; i2 < n; ++i2) {
            uint16_t b = table[int_bucket(static_cast<uint64_t>(static_cast<int64_t>(*(begin + i2)) - base), r)];
            bucket_cache[i2] = b;
            ++hist[b];
        }
        size_t* offset = static_cast<size_t*>(__builtin_alloca((k + 1) * sizeof(size_t)));
        offset[0] = 0;
        for (size_t j = 0; j < k; ++j) offset[j + 1] = offset[j] + hist[j];
        static temp_buffer<V> buf;
        buf.resize(static_cast<size_t>(n));
        V* tmp = buf.data();
        size_t* pos = static_cast<size_t*>(__builtin_alloca(k * sizeof(size_t)));
        for (size_t j = 0; j < k; ++j) pos[j] = offset[j];
        i2 = 0;
        for (; i2 + 4 <= n; i2 += 4) {
            QNQ_PREFETCH(&*(begin + i2 + PREFETCH_DIST));
            uint16_t b0 = bucket_cache[i2];
            uint16_t b1 = bucket_cache[i2 + 1];
            uint16_t b2 = bucket_cache[i2 + 2];
            uint16_t b3 = bucket_cache[i2 + 3];
            new (tmp + pos[b0]++) V(*(begin + i2));
            new (tmp + pos[b1]++) V(*(begin + i2 + 1));
            new (tmp + pos[b2]++) V(*(begin + i2 + 2));
            new (tmp + pos[b3]++) V(*(begin + i2 + 3));
        }
        for (; i2 < n; ++i2) {
            uint16_t b = bucket_cache[i2];
            new (tmp + pos[b]++) V(*(begin + i2));
        }
        for (ptrdiff_t j = 0; j < n; ++j) begin[j] = tmp[j];
        using IsTrivial = typename std::is_trivially_destructible<V>::type;
        detail::destroy_range(tmp, n, IsTrivial{});
        for (size_t j = 0; j < k; ++j) {
            size_t cnt = hist[j];
            if (cnt <= 1) continue;
            Iter sub_begin = begin + offset[j];
            Iter sub_end   = sub_begin + cnt;
            zsort_rec(sub_begin, sub_end, cmp);
        }
    }

    template<typename V, typename Iter, typename Compare>
    void zsort_rec_arith(Iter begin, Iter end, Compare cmp, std::false_type /* not integral, floating */) {
        ptrdiff_t n = end - begin;
        size_t m = static_cast<size_t>(n) < SAMPLE_SIZE ? static_cast<size_t>(n) : SAMPLE_SIZE;
        V sample[SAMPLE_SIZE];
        if (m == static_cast<size_t>(n)) {
            for (size_t i2 = 0; i2 < m; ++i2) sample[i2] = begin[i2];
        } else {
            size_t step = static_cast<size_t>(n) / m;
            for (size_t i2 = 0; i2 < m; ++i2) sample[i2] = begin[i2 * step];
        }
        insertion_sort(sample, sample + m, cmp);
        size_t k = compute_k(static_cast<size_t>(n));

        V min_val = *begin;
        V max_val = *begin;
        ptrdiff_t i = 1;
        for (; i + 4 <= n; i += 4) {
            V v0 = *(begin + i);
            V v1 = *(begin + i + 1);
            V v2 = *(begin + i + 2);
            V v3 = *(begin + i + 3);
            if (v0 < min_val) min_val = v0;
            if (v1 < min_val) min_val = v1;
            if (v2 < min_val) min_val = v2;
            if (v3 < min_val) min_val = v3;
            if (max_val < v0) max_val = v0;
            if (max_val < v1) max_val = v1;
            if (max_val < v2) max_val = v2;
            if (max_val < v3) max_val = v3;
        }
        for (; i < n; ++i) {
            V v = *(begin + i);
            if (v < min_val) min_val = v;
            if (max_val < v) max_val = v;
        }

        double min_d = static_cast<double>(min_val);
        double range = static_cast<double>(max_val) - min_d;
        if (QNQ_UNLIKELY(range <= 0.0)) {
            insertion_sort(begin, end, cmp);
            return;
        }
        double scale_f = MAX_BUCKETS_F / range;

        uint16_t table[MAX_BUCKETS];
        {
            double mf = static_cast<double>(m);
            for (size_t i2 = 0; i2 < MAX_BUCKETS; ++i2) {
                double t = static_cast<double>(i2 + 1) / MAX_BUCKETS_F;
                size_t target = static_cast<size_t>(t * mf);
                if (target >= m) target = m - 1;
                size_t bucket = static_cast<size_t>(static_cast<double>(target) / mf * static_cast<double>(k));
                if (bucket >= k) bucket = k - 1;
                table[i2] = static_cast<uint16_t>(bucket);
            }
        }
        static temp_buffer<uint16_t> bucket_buf;
        bucket_buf.resize(static_cast<size_t>(n));
        uint16_t* bucket_cache = bucket_buf.data();
        uint32_t* hist = static_cast<uint32_t*>(__builtin_alloca(k * sizeof(uint32_t)));
        std::memset(hist, 0, k * sizeof(uint32_t));
        ptrdiff_t i2 = 0;
        for (; i2 + 4 <= n; i2 += 4) {
            QNQ_PREFETCH(&*(begin + i2 + PREFETCH_DIST));
            uint16_t b0 = table[float_bucket(*(begin + i2),     min_val, scale_f)];
            uint16_t b1 = table[float_bucket(*(begin + i2 + 1), min_val, scale_f)];
            uint16_t b2 = table[float_bucket(*(begin + i2 + 2), min_val, scale_f)];
            uint16_t b3 = table[float_bucket(*(begin + i2 + 3), min_val, scale_f)];
            bucket_cache[i2]     = b0;
            bucket_cache[i2 + 1] = b1;
            bucket_cache[i2 + 2] = b2;
            bucket_cache[i2 + 3] = b3;
            ++hist[b0]; ++hist[b1]; ++hist[b2]; ++hist[b3];
        }
        for (; i2 < n; ++i2) {
            uint16_t b = table[float_bucket(*(begin + i2), min_val, scale_f)];
            bucket_cache[i2] = b;
            ++hist[b];
        }
        size_t* offset = static_cast<size_t*>(__builtin_alloca((k + 1) * sizeof(size_t)));
        offset[0] = 0;
        for (size_t j = 0; j < k; ++j) offset[j + 1] = offset[j] + hist[j];
        static temp_buffer<V> buf;
        buf.resize(static_cast<size_t>(n));
        V* tmp = buf.data();
        size_t* pos = static_cast<size_t*>(__builtin_alloca(k * sizeof(size_t)));
        for (size_t j = 0; j < k; ++j) pos[j] = offset[j];
        i2 = 0;
        for (; i2 + 4 <= n; i2 += 4) {
            QNQ_PREFETCH(&*(begin + i2 + PREFETCH_DIST));
            uint16_t b0 = bucket_cache[i2];
            uint16_t b1 = bucket_cache[i2 + 1];
            uint16_t b2 = bucket_cache[i2 + 2];
            uint16_t b3 = bucket_cache[i2 + 3];
            new (tmp + pos[b0]++) V(*(begin + i2));
            new (tmp + pos[b1]++) V(*(begin + i2 + 1));
            new (tmp + pos[b2]++) V(*(begin + i2 + 2));
            new (tmp + pos[b3]++) V(*(begin + i2 + 3));
        }
        for (; i2 < n; ++i2) {
            uint16_t b = bucket_cache[i2];
            new (tmp + pos[b]++) V(*(begin + i2));
        }
        for (ptrdiff_t j = 0; j < n; ++j) begin[j] = tmp[j];
        using IsTrivial = typename std::is_trivially_destructible<V>::type;
        detail::destroy_range(tmp, n, IsTrivial{});
        for (size_t j = 0; j < k; ++j) {
            size_t cnt = hist[j];
            if (cnt <= 1) continue;
            Iter sub_begin = begin + offset[j];
            Iter sub_end   = sub_begin + cnt;
            zsort_rec(sub_begin, sub_end, cmp);
        }
    }
}

template<typename Iter, typename Compare>
void zsort_rec(Iter begin, Iter end, Compare cmp) {
    using V = typename std::iterator_traits<Iter>::value_type;
    ptrdiff_t n = end - begin;
    if (n <= static_cast<ptrdiff_t>(INSERTION_SORT_THRESHOLD)) {
        insertion_sort(begin, end, cmp);
        return;
    }

    bool is_arith = std::is_arithmetic<V>::value;
    bool is_int   = std::is_integral<V>::value;
    V min_val{}, max_val{};
    if (is_arith) { min_val = *begin; max_val = *begin; }
    bool has_asc = false, has_desc = false;
    ptrdiff_t i = 1;
    for (; i + 4 <= n; i += 4) {
        V v0 = *(begin + i);
        V v1 = *(begin + i + 1);
        V v2 = *(begin + i + 2);
        V v3 = *(begin + i + 3);
        if (is_arith) {
            if (v0 < min_val) min_val = v0;
            if (v1 < min_val) min_val = v1;
            if (v2 < min_val) min_val = v2;
            if (v3 < min_val) min_val = v3;
            if (max_val < v0) max_val = v0;
            if (max_val < v1) max_val = v1;
            if (max_val < v2) max_val = v2;
            if (max_val < v3) max_val = v3;
        }
        if (QNQ_UNLIKELY(!has_asc || !has_desc)) {
            if (cmp(v0, *(begin + i - 1))) has_desc = true;
            else if (cmp(*(begin + i - 1), v0)) has_asc = true;
            if (cmp(v1, v0)) has_desc = true;
            else if (cmp(v0, v1)) has_asc = true;
            if (cmp(v2, v1)) has_desc = true;
            else if (cmp(v1, v2)) has_asc = true;
            if (cmp(v3, v2)) has_desc = true;
            else if (cmp(v2, v3)) has_asc = true;
        }
    }
    for (; i < n; ++i) {
        V v = *(begin + i);
        if (is_arith) {
            if (v < min_val) min_val = v;
            if (max_val < v) max_val = v;
        }
        if (QNQ_UNLIKELY(!has_asc || !has_desc)) {
            if (cmp(v, *(begin + i - 1))) has_desc = true;
            else if (cmp(*(begin + i - 1), v)) has_asc = true;
        }
    }
    if (!has_asc && !has_desc) return;
    if (has_asc && !has_desc)  return;
    if (has_desc && !has_asc)  { reverse_iter(begin, end); return; }
    if (handle_partial_ordered(begin, end, cmp)) return;
    if (counting_sort_if_possible(begin, end, cmp)) return;

    if (is_arith) {
        using IsIntT = typename std::is_integral<V>::type;
        detail::zsort_rec_arith<V>(begin, end, cmp, IsIntT{});
        return;
    }
    {
        size_t m = static_cast<size_t>(n) < SAMPLE_SIZE ? static_cast<size_t>(n) : SAMPLE_SIZE;
        V sample[SAMPLE_SIZE];
        if (m == static_cast<size_t>(n)) {
            for (size_t i2 = 0; i2 < m; ++i2) sample[i2] = begin[i2];
        } else {
            size_t step = static_cast<size_t>(n) / m;
            for (size_t i2 = 0; i2 < m; ++i2) sample[i2] = begin[i2 * step];
        }
        insertion_sort(sample, sample + m, cmp);
        size_t k = compute_k(static_cast<size_t>(n));
        V bucket_bounds[MAX_BUCKETS + 1];
        for (size_t j = 0; j <= k; ++j) {
            size_t idx = (j * m) / k;
            if (idx >= m) idx = m - 1;
            bucket_bounds[j] = sample[idx];
        }
        static temp_buffer<uint16_t> bucket_buf;
        bucket_buf.resize(static_cast<size_t>(n));
        uint16_t* bucket_cache = bucket_buf.data();
        uint32_t* hist = static_cast<uint32_t*>(__builtin_alloca(k * sizeof(uint32_t)));
        std::memset(hist, 0, k * sizeof(uint32_t));
        for (ptrdiff_t j = 0; j < n; ++j) {
            QNQ_PREFETCH(&*(begin + j + PREFETCH_DIST));
            const V& val = *(begin + j);
            size_t lo = 0, hi = k;
            while (lo < hi) {
                size_t mid = (lo + hi) >> 1;
                if (cmp(val, bucket_bounds[mid])) hi = mid;
                else                              lo = mid + 1;
            }
            size_t b = (lo == 0) ? 0 : (lo - 1);
            if (b >= k) b = k - 1;
            bucket_cache[j] = static_cast<uint16_t>(b);
            ++hist[b];
        }
        size_t* offset = static_cast<size_t*>(__builtin_alloca((k + 1) * sizeof(size_t)));
        offset[0] = 0;
        for (size_t j = 0; j < k; ++j) offset[j + 1] = offset[j] + hist[j];
        static temp_buffer<V> buf;
        buf.resize(static_cast<size_t>(n));
        V* tmp = buf.data();
        size_t* pos = static_cast<size_t*>(__builtin_alloca(k * sizeof(size_t)));
        for (size_t j = 0; j < k; ++j) pos[j] = offset[j];
        for (ptrdiff_t j = 0; j < n; ++j) {
            QNQ_PREFETCH(&*(begin + j + PREFETCH_DIST));
            uint16_t b = bucket_cache[j];
            new (tmp + pos[b]++) V(*(begin + j));
        }
        for (ptrdiff_t j = 0; j < n; ++j) begin[j] = tmp[j];
        using IsTrivial = typename std::is_trivially_destructible<V>::type;
        detail::destroy_range(tmp, n, IsTrivial{});
        for (size_t j = 0; j < k; ++j) {
            size_t cnt = hist[j];
            if (cnt <= 1) continue;
            Iter sub_begin = begin + offset[j];
            Iter sub_end   = sub_begin + cnt;
            zsort_rec(sub_begin, sub_end, cmp);
        }
    }
}

template<typename Iter, typename Compare>
inline void sort(Iter begin, Iter end, Compare cmp) {
    ptrdiff_t n = end - begin;
    if (n <= 1) return;
    if (QNQ_LIKELY(n <= static_cast<ptrdiff_t>(INSERTION_SORT_THRESHOLD))) {
        insertion_sort(begin, end, cmp);
        return;
    }
    {
        bool has_asc = false, has_desc = false;
        for (Iter it = begin + 1; it != end; ++it) {
            if (cmp(*it, *(it - 1)))      has_desc = true;
            else if (cmp(*(it - 1), *it)) has_asc  = true;
            if (has_asc && has_desc) break;
        }
        if (!has_asc && !has_desc) return;
        if (has_asc && !has_desc)  return;
        if (has_desc && !has_asc)  { reverse_iter(begin, end); return; }
    }
    if (counting_sort_if_possible(begin, end, cmp)) return;
    zsort_rec(begin, end, cmp);
}

} // namespace qnq_old
#endif


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

评测结果