代码

#include <algorithm>
#include <cstddef>
#include <functional>
#include <utility>

namespace blqs_core {

template <class T, class Compare>
static inline void sort2(T& a, T& b, Compare comp) {
    T x = a;
    T y = b;
    bool m = comp(x, y);
    a = m ? x : y;
    b = m ? y : x;
}

template <class T, class Compare>
static inline void median5(T& a, T& b, T& c, T& d, T& e, Compare comp) {
    sort2(a, b, comp);
    sort2(c, d, comp);
    sort2(a, c, comp);
    sort2(b, d, comp);
    sort2(b, c, comp);
    sort2(c, e, comp);
    sort2(b, c, comp);
}

template <class T, class Compare>
static inline void insertion_sort(T* left, T* right, Compare comp) {
    for (T* i = left + 1; i <= right; ++i) {
        T key = *i;
        T* j = i;
        while (j > left && comp(key, *(j - 1))) {
            *j = *(j - 1);
            --j;
        }
        *j = key;
    }
}

template <class T, class Compare>
static void heap_sort(T* left, T* right, Compare comp) {
    std::ptrdiff_t n = right - left + 1;
    if (n < 2) {
        return;
    }
    for (std::ptrdiff_t i = n / 2;;) {
        T key;
        if (i > 0) {
            key = left[--i];
        } else {
            --n;
            if (n == 0) {
                return;
            }
            key = left[n];
            left[n] = left[0];
        }
        std::ptrdiff_t parent = i;
        while (parent * 2 + 1 < n) {
            std::ptrdiff_t child = parent * 2 + 1;
            if (child + 1 < n && comp(left[child], left[child + 1])) {
                ++child;
            }
            if (!comp(key, left[child])) {
                break;
            }
            left[parent] = left[child];
            parent = child;
        }
        left[parent] = key;
    }
}

constexpr int SMALL_PARTITION_LIMIT = 256;
constexpr int SIDE_BUFFER_SIZE = 1024;
constexpr int UNROLL_COUNT = 16;

template <class T, class Compare>
static T* partition_small(T* left, T* right, Compare comp) {
    T* outer_left = left;
    T* pivot_pos = left + (right - left) / 2;

    T left_1 = left[1];
    T left_2 = left[2];
    T pivot = *pivot_pos;
    T right_1 = right[-1];
    T right_0 = *right;

    median5(left_1, left_2, pivot, right_1, right_0, comp);

    left[1] = left_1;
    left[2] = left_2;
    right[-1] = right_1;
    *right = right_0;

    left += 3;
    right -= 2;
    *pivot_pos = *outer_left;

    T side_buffer[SMALL_PARTITION_LIMIT];
    T* side_write = side_buffer;
    T* left_write = left;

    while (left <= right) {
        bool goes_left = comp(*left, pivot);
        *left_write = *side_write = *left++;
        left_write += goes_left;
        side_write += !goes_left;
    }

    T* side_read = side_buffer;
    T* side_dest = left_write;
    while (side_read < side_write) {
        *side_dest++ = *side_read++;
    }

    --left_write;
    *outer_left = *left_write;
    *left_write = pivot;
    return left_write;
}

template <class T, class Compare>
static T* partition_large(T* left, T* right, Compare comp) {
    T* outer_left = left;
    T* pivot_pos = left + (right - left) / 2;
    T pivot = *pivot_pos;

    median5(left[1], left[2], left[3], left[4], left[5], comp);
    median5(left[21], left[22], left[23], left[24], left[25], comp);
    median5(pivot_pos[-2], pivot_pos[-1], pivot, pivot_pos[1], pivot_pos[2], comp);
    median5(right[-14], right[-13], right[-12], right[-11], right[-10], comp);
    median5(right[-4], right[-3], right[-2], right[-1], right[0], comp);
    median5(left[3], left[23], pivot, right[-12], right[-2], comp);

    ++left;
    *pivot_pos = *outer_left;

    while (comp(*left, pivot)) {
        ++left;
    }

    if (left >= outer_left + 12) {
        *pivot_pos = pivot;
        for (T* p = outer_left + 1; p <= right; ++p) {
            if (comp(*p, *(p - 1))) {
                *pivot_pos = *outer_left;
                goto not_already_sorted;
            }
        }
        return nullptr;
    }

not_already_sorted:
    T side_buffer[SIDE_BUFFER_SIZE];
    T* left_write = left;
    T* right_write = right;
    T* side_write = side_buffer;

    while (side_write < side_buffer + SIDE_BUFFER_SIZE - UNROLL_COUNT && left <= right - UNROLL_COUNT) {
        for (int i = UNROLL_COUNT; i--;) {
            bool goes_left = comp(*right, pivot);
            *right_write = *side_write = *right--;
            right_write -= !goes_left;
            side_write += goes_left;
        }
    }

    while (side_write < side_buffer + SIDE_BUFFER_SIZE - UNROLL_COUNT && left <= right) {
        bool goes_left = comp(*right, pivot);
        *right_write = *side_write = *right--;
        right_write -= !goes_left;
        side_write += goes_left;
    }

    while (left <= right - UNROLL_COUNT) {
        while (right_write > right + UNROLL_COUNT && left <= right - UNROLL_COUNT) {
            for (int i = UNROLL_COUNT; i--;) {
                bool goes_left = comp(*left, pivot);
                *left_write = *right_write = *left++;
                left_write += goes_left;
                right_write -= !goes_left;
            }
        }
        while (left_write < left - UNROLL_COUNT && left <= right - UNROLL_COUNT) {
            for (int i = UNROLL_COUNT; i--;) {
                bool goes_left = comp(*right, pivot);
                *right_write = *left_write = *right--;
                right_write -= !goes_left;
                left_write += goes_left;
            }
        }
    }

    while (right_write > right && left <= right) {
        bool goes_left = comp(*left, pivot);
        *left_write = *right_write = *left++;
        left_write += goes_left;
        right_write -= !goes_left;
    }

    while (left <= right) {
        bool goes_left = comp(*right, pivot);
        *right_write = *left_write = *right--;
        right_write -= !goes_left;
        left_write += goes_left;
    }

    for (T* p = side_buffer; p < side_write; ++p) {
        *left_write++ = *p;
    }

    *outer_left = *right_write;
    *right_write = pivot;
    return right_write;
}

template <class T, class Compare>
static void blqsort(T* left, T* right, Compare comp) {
    while (true) {
        std::ptrdiff_t size_minus_one = right - left;

        if (size_minus_one <= 24) {
            insertion_sort(left, right, comp);
            return;
        }

        T* middle;

        if (size_minus_one <= SMALL_PARTITION_LIMIT) {
            middle = partition_small(left, right, comp);
        } else {
            middle = partition_large(left, right, comp);

            if (middle == nullptr) {
                return;
            }

            if ((middle - left) * 16 < size_minus_one || (right - middle) * 16 < size_minus_one) {
                if (middle > left) {
                    heap_sort(left, middle - 1, comp);
                }

                T pivot = *middle;
                ++middle;

                for (T* p = middle; p <= right; ++p) {
                    if (!comp(pivot, *p)) {
                        std::swap(*middle, *p);
                        ++middle;
                    }
                }

                if (middle <= right) {
                    heap_sort(middle, right, comp);
                }
                return;
            }
        }

        if (middle - left < right - middle) {
            if (middle > left) {
                blqsort(left, middle - 1, comp);
            }
            left = middle + 1;
        } else {
            if (middle < right) {
                blqsort(middle + 1, right, comp);
            }
            right = middle - 1;
        }
    }
}

template <class T, class Compare>
void sort(T* first, T* last, Compare comp) {
    if (last - first < 2) {
        return;
    }
    blqsort(first, last - 1, comp);
}

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

}

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

评测结果