代码

// ============================================================================
// duck.ac/problem/1001  测测你的排序
//
//   接口：void sort(unsigned *a, int n);      n = 100'000'000，原地升序
//   限制：5 s / 819200 KB
//
// 提交环境（judge FAQ + 题目页的下拉框原文）：
//   g++ 9.3.0，编译选项 `g++ -static -U_FORTIFY_SOURCE -O2`，
//   语言可选 C / C++ / C++11 / C++14 / C++17（没有 C++20）。
//
// 因此本文件是 include/sort.cc 的 **C++14 可编译移植**，逐函数一一对应：
//   * <concepts>/<ranges> 约束去掉，迭代器模板改写成指针模板 (T* first, T* last)；
//   * std::ranges::less    -> detail::less
//   * std::ranges::swap    -> std::swap
//   * std::integral<T>     -> std::is_integral<T>::value（tag dispatch 代替 if constexpr）
//   * std::identity        -> detail::identity
// 算法结构、阈值（512 / 64 / 24 / 16 / 8）、分支、注释含义与 include/sort.cc 完全一致；
// comp/proj 组合（comp_proj）也保留，保证热点路径与 include/sort.cc 等价。
//
// 提交方式：整个文件粘进题目页的代码框，语言选 C++17（选 C++ 也行，本文件兼容 C++14）。
// ============================================================================

#include <cstddef>
#include <type_traits>
#include <utility>
#include <vector>

namespace duck {

namespace detail {

// std::ranges::less 的等价物
struct less {
    template <class T, class U>
    constexpr bool operator()(const T& a, const U& b) const { return a < b; }
};

// std::identity 的等价物（题目接口用不到 proj，保留只为与 include/sort.cc 同构）
struct identity {
    template <class T>
    constexpr T&& operator()(T&& t) const noexcept {
        return static_cast<T&&>(t);
    }
};

// 把 comp 与 proj 组合成单一的“比较投影后值”的谓词
template <class Comp, class Proj>
struct comp_proj {
    Comp comp;
    Proj proj;

    template <class T, class U>
    constexpr bool operator()(const T& a, const U& b) const {
        return static_cast<bool>(comp(proj(a), proj(b)));
    }
};

// 在比较器意义下 a 与 b 等价
template <class Comp, class V>
constexpr bool equiv(const Comp& comp, const V& a, const V& b) {
    return !comp(a, b) && !comp(b, a);
}

// 小数组插入排序
template <class T, class Comp>
constexpr void insertion_sort(T* first, T* last, const Comp& comp) {
    if (last - first <= 1) return;
    for (T* i = first + 1; i != last; ++i) {
        T key = std::move(*i);
        T* j = i;
        while (j != first && comp(key, *(j - 1))) {
            *j = std::move(*(j - 1));
            --j;
        }
        *j = std::move(key);
    }
}

// 返回三位置中值所在指针（纯分支，不交换）
template <class T, class Comp>
constexpr T* median3_pos(T* a, T* b, T* c, const Comp& comp) {
    if (comp(*a, *b)) {
        if (comp(*b, *c)) return b;
        return comp(*a, *c) ? c : a;
    } else {
        if (comp(*a, *c)) return a;
        return comp(*b, *c) ? c : b;
    }
}

// 三数取中，把中值换到 *first
template <class T, class Comp>
constexpr void median_of_three(T* first, T* last, const Comp& comp) {
    T* lo  = first + 1;
    T* hi  = last - 2;
    T* mid = first + (last - first) / 2;
    std::swap(*median3_pos(lo, mid, hi, comp), *first);
}

// ninther：九个样本的三组中值再取中值，换到 *first
template <class T, class Comp>
constexpr void median_ninther(T* first, T* last, const Comp& comp) {
    const std::ptrdiff_t n = last - first;
    const std::ptrdiff_t e = n / 8;
    T* mid = first + n / 2;
    T* m1 = median3_pos(first + 1, first + 1 + e, first + 1 + 2 * e, comp);
    T* m2 = median3_pos(mid - e, mid, mid + e, comp);
    T* m3 = median3_pos(last - 2 - 2 * e, last - 2 - e, last - 2, comp);
    std::swap(*median3_pos(m1, m2, m3, comp), *first);
}

template <class T>
struct partition_result {
    T* lt_end;    // [first, lt_end)  仅含小于 pivot 的键
    T* gt_begin;  // [gt_begin, last) 仅含大于 pivot 的键
};

// 二路划分：不检查相等，适合键互异的输入
template <class T, class Comp>
constexpr partition_result<T> two_way_partition(T* first, T* last, const Comp& comp) {
    const T pivot = *first;
    T* i = first;
    T* j = last;
    T* p = first;  // dummy collector，与原算法保持一致

    for (;;) {
        while (true) {
            ++i;
            if (!comp(*i, pivot)) break;
            if (i == last - 1) break;
        }
        while (true) {
            --j;
            if (!comp(pivot, *j)) break;
            if (j == first) break;
        }
        if (i >= j) break;
        std::swap(*i, *j);
    }

    i = j + 1;
    for (T* k = first; k <= p; ++k, --j) std::swap(*k, *j);
    return {j + 1, i};
}

// Bentley-McIlroy 三路划分：相等键收集到两端，再换到中间
template <class T, class Comp>
constexpr partition_result<T> ternary_partition(T* first, T* last, const Comp& comp) {
    const T pivot = *first;
    T* i = first;
    T* j = last;
    T* p = first;
    T* q = last;

    for (;;) {
        while (true) {
            ++i;
            if (!comp(*i, pivot)) break;
            if (i == last - 1) break;
        }
        while (true) {
            --j;
            if (!comp(pivot, *j)) break;
            if (j == first) break;
        }
        if (i >= j) break;
        std::swap(*i, *j);
        if (equiv(comp, *i, pivot)) { ++p; std::swap(*p, *i); }
        if (equiv(comp, *j, pivot)) { --q; std::swap(*q, *j); }
    }

    i = j + 1;
    for (T* k = first; k <= p; ++k, --j) std::swap(*k, *j);
    for (T* k = last - 1; k >= q; --k, ++i) std::swap(*k, *i);
    return {j + 1, i};
}

// 下沉调整：[0, n) 堆中把 first[parent] 下沉到合适位置
// （heap_sort 专用，数值索引版，避免指针反复加减）
template <class T, class Comp>
constexpr void sift_down(T* first, std::ptrdiff_t n, std::ptrdiff_t parent, const Comp& comp) {
    T value = std::move(first[parent]);
    for (;;) {
        std::ptrdiff_t child = 2 * parent + 1;
        if (child >= n) break;
        if (child + 1 < n && comp(first[child], first[child + 1])) ++child;
        if (comp(value, first[child])) {
            first[parent] = std::move(first[child]);
            parent = child;
        } else break;
    }
    first[parent] = std::move(value);
}

// 原地堆排序：O(n log n) 最坏保证，作为深度回退的兜底路径
template <class T, class Comp>
constexpr void heap_sort(T* first, T* last, const Comp& comp) {
    const std::ptrdiff_t n = last - first;
    if (n < 2) return;
    for (std::ptrdiff_t i = n / 2; i > 0; --i) sift_down(first, n, i - 1, comp);
    for (std::ptrdiff_t end = n - 1; end > 0; --end) {
        std::swap(first[0], first[end]);
        sift_down(first, end, 0, comp);
    }
}

// 深度上限：2 * floor(log2(n))，达到即回退堆排序
constexpr std::ptrdiff_t depth_limit(std::ptrdiff_t n) {
    std::ptrdiff_t d = 0;
    while (n > 1) { n >>= 1; ++d; }
    return 2 * d;
}

// 整段已序的快速出口：一次线性扫描同时检查“非递减”和“非递增”
template <class T, class Comp>
constexpr bool presorted(T* first, T* last, const Comp& comp) {
    const std::ptrdiff_t n = last - first;
    if (n < 2) return true;
    bool inc = true, dec = true;
    for (T* i = first + 1; i != last; ++i) {
        if (comp(*i, *(i - 1))) inc = false;        // 出现下降
        else if (comp(*(i - 1), *i)) dec = false;   // 出现上升
        if (!inc && !dec) return false;
    }
    if (inc) return true;
    for (T* a = first, *b = last - 1; a < b; ++a, --b) std::swap(*a, *b);
    return true;
}

// 跨度判据（仅整数类型）：采样值域跨度 span 远小于 n => 平均每个键有 n/span >= 8 个副本。
// 非整数类型恒 false（用 tag dispatch 代替 if constexpr，保持 C++14 可编译）。
template <class T>
constexpr bool span_means_duplicates(const std::vector<T>&, std::ptrdiff_t, std::false_type) {
    return false;
}

template <class T>
constexpr bool span_means_duplicates(const std::vector<T>& sample, std::ptrdiff_t n, std::true_type) {
    typedef typename std::make_unsigned<T>::type U;
    const U span = static_cast<U>(sample.back()) - static_cast<U>(sample.front());
    return span < static_cast<U>(n) / 8;
}

// 是否值得走三路：两个判据，都基于跨步采样的 64 个点
//   1) 碰撞：采样值中出现相等 => 值域密到重复键占主导；
//   2) 跨度：整数类型下 span 远小于 n => 平均每个键有大量副本。
template <class T, class Comp>
constexpr bool has_duplicates(T* first, T* last, const Comp& comp) {
    const std::ptrdiff_t n = last - first;
    if (n < 512) return false;
    const std::ptrdiff_t s = n < 64 ? n : 64;   // 采样点数
    std::vector<T> sample;
    sample.reserve(static_cast<std::size_t>(s));
    for (std::ptrdiff_t k = 0; k < s; ++k) sample.push_back(first[k * n / s]);
    for (std::size_t i = 1; i < sample.size(); ++i) {           // 采样点插入排序
        T v = sample[i];
        std::size_t j = i;
        while (j > 0 && comp(v, sample[j - 1])) { sample[j] = sample[j - 1]; --j; }
        sample[j] = v;
    }
    for (std::size_t i = 1; i < sample.size(); ++i)              // 相邻等值 => 有重复
        if (equiv(comp, sample[i - 1], sample[i])) return true;
    return span_means_duplicates(
        sample, n, std::integral_constant<bool, std::is_integral<T>::value>());
}

// 三路路径：适合大量重复键
// 救场机制：depth 用尽时，若从未用过 ninther 救场，则 ninther 重选 pivot 一刀并重置深度；
// 再次用尽（真 killer，连 ninther 都被骗）才整体 heapsort。最坏仍 O(n log n)。
template <class T, class Comp>
constexpr void sort_ternary(T* first, T* last, const Comp& comp,
                            std::ptrdiff_t depth, bool& ninther_used) {
    while (last - first > 16) {
        bool force_ninther = false;
        if (depth <= 0) {
            if (!ninther_used) {
                ninther_used = true;
                force_ninther = true;
                depth = depth_limit(last - first);
            } else {
                heap_sort(first, last, comp);
                return;
            }
        }
        --depth;
        if (force_ninther || last - first > 64) median_ninther(first, last, comp);
        else                                    median_of_three(first, last, comp);

        partition_result<T> r = ternary_partition(first, last, comp);

        if (r.lt_end - first < last - r.gt_begin) {
            sort_ternary(first, r.lt_end, comp, depth, ninther_used);
            first = r.gt_begin;
        } else {
            sort_ternary(r.gt_begin, last, comp, depth, ninther_used);
            last = r.lt_end;
        }
    }
    insertion_sort(first, last, comp);
}

// 二路路径：键互异时最快（救场机制同 sort_ternary）
template <class T, class Comp>
constexpr void sort_two_way(T* first, T* last, const Comp& comp,
                            std::ptrdiff_t depth, bool& ninther_used) {
    while (last - first > 24) {
        bool retried = false;
        bool force_ninther = false;
        if (depth <= 0) {
            if (!ninther_used) {
                ninther_used = true;
                force_ninther = true;
                depth = depth_limit(last - first);
            } else {
                heap_sort(first, last, comp);
                return;
            }
        }
        --depth;
        if (force_ninther) median_ninther(first, last, comp);
        else               median_of_three(first, last, comp);

        partition_result<T> r = two_way_partition(first, last, comp);

        // 分区失衡检测（pdqsort 式）：大区间切得太偏时换 ninther 重分区一次，
        // 仍失衡说明是病态输入，整段改用 heapsort。
        if (!retried) {
            const std::ptrdiff_t n = last - first;
            const std::ptrdiff_t left = r.lt_end - first;
            const std::ptrdiff_t right = last - r.gt_begin;
            const std::ptrdiff_t smaller = left < right ? left : right;
            if (n >= 512 && smaller * 8 < n) {
                retried = true;
                median_ninther(first, last, comp);
                partition_result<T> r2 = two_way_partition(first, last, comp);
                const std::ptrdiff_t l2 = r2.lt_end - first;
                const std::ptrdiff_t r2len = last - r2.gt_begin;
                if ((l2 < r2len ? l2 : r2len) * 8 >= n) {
                    r.lt_end = r2.lt_end;
                    r.gt_begin = r2.gt_begin;
                } else {
                    heap_sort(first, last, comp);
                    return;
                }
            }
        }

        if (r.lt_end - first < last - r.gt_begin) {
            sort_two_way(first, r.lt_end, comp, depth, ninther_used);
            first = r.gt_begin;
        } else {
            sort_two_way(r.gt_begin, last, comp, depth, ninther_used);
            last = r.lt_end;
        }
    }
    insertion_sort(first, last, comp);
}

} // namespace detail

// 与 include/sort.cc 的 algo::sort 同一入口（无 proj 参数：题目接口只排 unsigned）
template <class T, class Comp>
void sort(T* first, T* last, const Comp& comp) {
    const std::ptrdiff_t n = last - first;
    if (n <= 1) return;

    detail::comp_proj<Comp, detail::identity> cp{comp, detail::identity()};
    std::ptrdiff_t depth = detail::depth_limit(n);
    bool ninther_used = false;

    if (n >= 512 && detail::presorted(first, last, cp)) return;
    if (detail::has_duplicates(first, last, cp))
        detail::sort_ternary(first, last, cp, depth, ninther_used);
    else
        detail::sort_two_way(first, last, cp, depth, ninther_used);
}

template <class T>
void sort(T* first, T* last) {
    duck::sort(first, last, detail::less());
}

} // namespace duck

// ---------------------------------------------------------------------------
// 题目要求的接口
// ---------------------------------------------------------------------------
void sort(unsigned *a, int n) {
    duck::sort(a, a + n, duck::detail::less());
}

评测结果