#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);
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 3.062 s | 953 MB + 832 KB | Memory Limit Exceeded | Score: 0 | 显示更多 |