#ifndef QNQ_ALGORITHM_H
#define QNQ_ALGORITHM_H
#include <cstddef>
#include <type_traits>
#include <cmath>
#include <cstring>
#include <new>
#include <iterator>
#include <cstdint>
#if defined(__AVX2__)
#include <immintrin.h>
#endif
namespace qnq {
#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 = 32;
static constexpr size_t COUNTING_SORT_RANGE_LIMIT = 65000;
static constexpr size_t PARTIAL_ORDER_MIN_SIZE = 128;
static constexpr size_t SAMPLE_SIZE = 256; // ★ 128 → 256
static constexpr size_t MAX_BUCKETS = 4096;
static constexpr size_t PREFETCH_DIST = 32;
static constexpr double MAX_BUCKETS_F = (double)MAX_BUCKETS;
static constexpr size_t PARTIAL_ORDER_NUM = 1;
static constexpr size_t PARTIAL_ORDER_DEN = 5;
static constexpr size_t CONC_MIN_SIZE = 100'000;
static constexpr double CONC_LOW = 0.55;
static constexpr double CONC_HIGH = 0.72;
static constexpr size_t SMALL_BUCKET_THRESHOLD = 128;
static constexpr size_t DUAL_HIST_THRESHOLD = 2'000'000;
static constexpr size_t SIMD_BUCKET_THRESHOLD = 1024; // ★ 4096 → 1024
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());
template<typename T>
class temp_buffer {
T* data_; size_t capacity_;
public:
temp_buffer() : data_(nullptr), capacity_(0) {}
~temp_buffer() {
if (data_) {
if constexpr (!std::is_trivially_destructible_v<T>) {
for (size_t i = 0; i < capacity_; ++i) data_[i].~T();
}
operator delete(data_);
}
}
void resize(size_t n) {
if (QNQ_LIKELY(n <= capacity_)) return;
if (data_) {
if constexpr (!std::is_trivially_destructible_v<T>) {
for (size_t i = 0; i < capacity_; ++i) data_[i].~T();
}
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((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++];
if constexpr (!std::is_trivially_destructible_v<V>) {
for (ptrdiff_t x = 0; x < n1; ++x) tmp[x].~V();
}
}
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;
}
}
template<typename Iter, typename V>
inline void counting_sort_range(Iter begin, Iter end, V min_val, V max_val) {
ptrdiff_t n = end - begin;
if (n <= 1) return;
using wide = std::conditional_t<sizeof(V) < 4, int64_t, V>;
wide range = (wide)max_val - (wide)min_val;
if (range < 0) return;
size_t r = (size_t)range + 1;
uint32_t* counts = static_cast<uint32_t*>(__builtin_alloca(r * sizeof(uint32_t)));
std::memset(counts, 0, r * sizeof(uint32_t));
for (Iter it = begin; it != end; ++it)
++counts[(size_t)((wide)*it - (wide)min_val)];
uint32_t total = 0;
for (size_t i = 0; i < r; ++i) {
uint32_t c = counts[i]; counts[i] = total; total += c;
}
static temp_buffer<V> buf;
buf.resize((size_t)n);
V* tmp = buf.data();
for (Iter it = begin; it != end; ++it) {
size_t idx = (size_t)((wide)*it - (wide)min_val);
new (tmp + counts[idx]++) V(*it);
}
if constexpr (std::is_pointer_v<Iter> && std::is_trivially_copyable_v<V>) {
std::memcpy((void*)&*begin, tmp, (size_t)n * sizeof(V));
} else {
for (ptrdiff_t i = 0; i < n; ++i) begin[i] = tmp[i];
}
if constexpr (!std::is_trivially_destructible_v<V>) {
for (ptrdiff_t i = 0; i < n; ++i) tmp[i].~V();
}
}
template<typename Iter, typename Compare>
inline bool handle_partial_ordered(Iter begin, Iter end, Compare cmp) {
ptrdiff_t n = end - begin;
if (n <= (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;
ptrdiff_t total_sorted = prefix_len + suffix_len;
if (total_sorted * PARTIAL_ORDER_DEN <= n * PARTIAL_ORDER_NUM) return false;
Iter mid_begin = prefix_end + 1;
Iter mid_end = suffix_start;
if (mid_begin < end) {
qnq::sort(mid_begin, end, cmp);
}
if (prefix_len > 0 && mid_begin < end) {
stable_merge(begin, mid_begin, end, cmp);
}
return true;
}
QNQ_FORCE_INLINE size_t compute_k(size_t n) {
size_t k;
if (n < 200'000) {
k = (size_t)(3.5 * std::sqrt((double)n));
if (k < 512) k = 512;
if (k > 2048) k = 2048;
} else if (n < 2'000'000) {
k = (size_t)(2.5 * std::sqrt((double)n));
if (k < 1024) k = 1024;
if (k > 4096) k = 4096;
} else {
k = (size_t)(0.5 * std::sqrt((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;
}
template<typename V>
QNQ_FORCE_INLINE size_t compute_k_adaptive(size_t n, const V* sorted_sample, size_t m) {
size_t k = compute_k(n);
if (n < CONC_MIN_SIZE || m < 32) return k;
double range_f = (double)sorted_sample[m - 1] - (double)sorted_sample[0];
if (range_f <= 0.0) return k;
double p25 = (double)sorted_sample[m / 4];
double p75 = (double)sorted_sample[m * 3 / 4];
double conc = (p75 - p25) / range_f;
if (conc < CONC_LOW) {
k = (size_t)((double)k * 1.5);
if (k > MAX_BUCKETS) k = MAX_BUCKETS;
} else if (conc > CONC_HIGH) {
k = (size_t)((double)k * 0.8);
if (k < 512) k = 512;
}
return k;
}
QNQ_FORCE_INLINE uint16_t int_bucket(uint64_t diff, uint64_t recip) {
uint64_t prod = diff * recip;
uint32_t idx = (uint32_t)(prod >> 32);
return (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 = ((double)val - (double)min_val) * scale_f;
size_t idx = (size_t)norm;
return (uint16_t)(QNQ_LIKELY(idx < MAX_BUCKETS) ? idx : MAX_BUCKETS - 1);
}
template<typename V>
QNQ_FORCE_INLINE void build_table(uint16_t* table, size_t k, size_t m,
const V* sorted_sample,
double min_val_d, double max_val_d)
{
double range_d = max_val_d - min_val_d;
if (range_d <= 0.0) {
for (size_t i = 0; i < MAX_BUCKETS; ++i) table[i] = 0;
return;
}
double sample_min = (double)sorted_sample[0];
double sample_max = (double)sorted_sample[m - 1];
double inner_range = sample_max - sample_min;
if (inner_range <= 0.0 || inner_range < range_d * 0.5) {
for (size_t i = 0; i < MAX_BUCKETS; ++i) {
size_t bucket = (i * k) / MAX_BUCKETS;
if (bucket >= k) bucket = k - 1;
table[i] = (uint16_t)bucket;
}
return;
}
size_t p = 0;
for (size_t i = 0; i < MAX_BUCKETS; ++i) {
double val_target = min_val_d + (double)(i + 1) / MAX_BUCKETS_F * range_d;
size_t bucket;
if (val_target <= sample_min) {
double denom = sample_min - min_val_d;
double frac = (denom > 0.0) ? (val_target - min_val_d) / denom : 0.0;
bucket = (size_t)(frac * (double)k / (double)m);
if (bucket >= k) bucket = k - 1;
} else if (val_target >= sample_max) {
double denom = max_val_d - sample_max;
double frac = (denom > 0.0) ? (val_target - sample_max) / denom : 0.0;
double base = (double)(m - 1) / (double)m * (double)k;
bucket = (size_t)(base + frac * (double)k / (double)m);
if (bucket >= k) bucket = k - 1;
} else {
while (p < m && (double)sorted_sample[p] < val_target) ++p;
bucket = (p * k) / m;
if (bucket >= k) bucket = k - 1;
}
table[i] = (uint16_t)bucket;
}
}
#if defined(__AVX2__)
QNQ_FORCE_INLINE size_t simd_bucket_int32(
const int32_t* data, size_t n, size_t start,
double min_val_d, double scale_f,
const uint16_t* table, uint16_t* bucket_cache,
uint32_t* hist, uint32_t* histB)
{
__m256 fmin = _mm256_set1_ps((float)min_val_d);
__m256 fscale = _mm256_set1_ps((float)scale_f);
size_t i = start;
size_t i_end = (n >= 8) ? (n - 7) : 0;
for (; i < i_end; i += 8) {
__m256i v = _mm256_loadu_si256((const __m256i*)(data + i));
__m256 f = _mm256_cvtepi32_ps(v);
f = _mm256_mul_ps(_mm256_sub_ps(f, fmin), fscale);
__m256i idx_vec = _mm256_cvttps_epi32(f);
alignas(32) int32_t idx_arr[8];
_mm256_store_si256((__m256i*)idx_arr, idx_vec);
uint16_t b0 = table[(uint32_t)idx_arr[0] < MAX_BUCKETS ? idx_arr[0] : MAX_BUCKETS - 1];
uint16_t b1 = table[(uint32_t)idx_arr[1] < MAX_BUCKETS ? idx_arr[1] : MAX_BUCKETS - 1];
uint16_t b2 = table[(uint32_t)idx_arr[2] < MAX_BUCKETS ? idx_arr[2] : MAX_BUCKETS - 1];
uint16_t b3 = table[(uint32_t)idx_arr[3] < MAX_BUCKETS ? idx_arr[3] : MAX_BUCKETS - 1];
uint16_t b4 = table[(uint32_t)idx_arr[4] < MAX_BUCKETS ? idx_arr[4] : MAX_BUCKETS - 1];
uint16_t b5 = table[(uint32_t)idx_arr[5] < MAX_BUCKETS ? idx_arr[5] : MAX_BUCKETS - 1];
uint16_t b6 = table[(uint32_t)idx_arr[6] < MAX_BUCKETS ? idx_arr[6] : MAX_BUCKETS - 1];
uint16_t b7 = table[(uint32_t)idx_arr[7] < MAX_BUCKETS ? idx_arr[7] : MAX_BUCKETS - 1];
bucket_cache[i] = b0; bucket_cache[i + 1] = b1;
bucket_cache[i + 2] = b2; bucket_cache[i + 3] = b3;
bucket_cache[i + 4] = b4; bucket_cache[i + 5] = b5;
bucket_cache[i + 6] = b6; bucket_cache[i + 7] = b7;
if (histB) {
++hist[b0]; ++histB[b1]; ++hist[b2]; ++histB[b3];
++hist[b4]; ++histB[b5]; ++hist[b6]; ++histB[b7];
} else {
++hist[b0]; ++hist[b1]; ++hist[b2]; ++hist[b3];
++hist[b4]; ++hist[b5]; ++hist[b6]; ++hist[b7];
}
}
return i;
}
#endif
#if defined(__AVX2__)
QNQ_FORCE_INLINE void minmax_int32_avx2(const int32_t* data, size_t n,
int32_t& out_min, int32_t& out_max) {
if (n < 8) {
out_min = out_max = data[0];
for (size_t i = 1; i < n; ++i) {
if (data[i] < out_min) out_min = data[i];
if (data[i] > out_max) out_max = data[i];
}
return;
}
__m256i vmin = _mm256_loadu_si256((const __m256i*)data);
__m256i vmax = vmin;
size_t i = 8;
for (; i + 8 <= n; i += 8) {
__m256i v = _mm256_loadu_si256((const __m256i*)(data + i));
vmin = _mm256_min_epi32(vmin, v);
vmax = _mm256_max_epi32(vmax, v);
}
__m128i lo, hi, m128;
lo = _mm256_castsi256_si128(vmin); hi = _mm256_extracti128_si256(vmin, 1);
m128 = _mm_min_epi32(lo, hi);
m128 = _mm_min_epi32(m128, _mm_shuffle_epi32(m128, _MM_SHUFFLE(1,0,3,2)));
m128 = _mm_min_epi32(m128, _mm_shuffle_epi32(m128, _MM_SHUFFLE(2,3,0,1)));
out_min = _mm_cvtsi128_si32(m128);
lo = _mm256_castsi256_si128(vmax); hi = _mm256_extracti128_si256(vmax, 1);
m128 = _mm_max_epi32(lo, hi);
m128 = _mm_max_epi32(m128, _mm_shuffle_epi32(m128, _MM_SHUFFLE(1,0,3,2)));
m128 = _mm_max_epi32(m128, _mm_shuffle_epi32(m128, _MM_SHUFFLE(2,3,0,1)));
out_max = _mm_cvtsi128_si32(m128);
for (; i < n; ++i) {
if (data[i] < out_min) out_min = data[i];
if (data[i] > out_max) out_max = data[i];
}
}
#endif
#if defined(__AVX2__)
QNQ_FORCE_INLINE int detect_order_simd_phase2(const int32_t* data, size_t n, bool has_asc) {
if (has_asc) {
size_t i = 32;
for (; i + 8 <= n; i += 8) {
__m256i prev = _mm256_loadu_si256((const __m256i*)(data + i - 1));
__m256i curr = _mm256_loadu_si256((const __m256i*)(data + i));
__m256i bad = _mm256_cmpgt_epi32(prev, curr);
if (_mm256_movemask_ps(_mm256_castsi256_ps(bad)) != 0) return 0;
}
for (; i < n; ++i) if (data[i] < data[i-1]) return 0;
return 1;
} else {
size_t i = 32;
for (; i + 8 <= n; i += 8) {
__m256i prev = _mm256_loadu_si256((const __m256i*)(data + i - 1));
__m256i curr = _mm256_loadu_si256((const __m256i*)(data + i));
__m256i bad = _mm256_cmpgt_epi32(curr, prev);
if (_mm256_movemask_ps(_mm256_castsi256_ps(bad)) != 0) return 0;
}
for (; i < n; ++i) if (data[i-1] < data[i]) return 0;
return -1;
}
}
#endif
template<typename Iter, typename Compare>
QNQ_FORCE_INLINE int fast_detect_order(Iter begin, Iter end, Compare cmp) {
using V = typename std::iterator_traits<Iter>::value_type;
constexpr bool use_simd =
std::is_pointer_v<Iter> &&
std::is_same_v<std::remove_cv_t<V>, int32_t> &&
std::is_same_v<std::decay_t<Compare>, default_less<int32_t>>;
ptrdiff_t n = end - begin;
if (n < 2) return 2;
ptrdiff_t phase1_end = (n < 32) ? n : 32;
bool has_asc = false, has_desc = false;
for (ptrdiff_t i = 1; i < phase1_end; ++i) {
if (cmp(*(begin + i), *(begin + i - 1))) has_desc = true;
else if (cmp(*(begin + i - 1), *(begin + i))) has_asc = true;
if (has_asc && has_desc) return 0;
}
if (!has_asc && !has_desc) {
for (ptrdiff_t i = phase1_end; i < n; ++i) {
if (cmp(*(begin + i), *(begin + i - 1))) has_desc = true;
else if (cmp(*(begin + i - 1), *(begin + i))) has_asc = true;
if (has_asc && has_desc) return 0;
}
if (!has_asc && !has_desc) return 2;
return has_asc ? 1 : -1;
}
if (n <= 32) return has_asc ? 1 : -1;
if constexpr (use_simd) {
#if defined(__AVX2__)
return detect_order_simd_phase2(begin, (size_t)n, has_asc);
#else
if (has_asc) {
for (ptrdiff_t i = 32; i < n; ++i) if (cmp(*(begin+i), *(begin+i-1))) return 0;
return 1;
} else {
for (ptrdiff_t i = 32; i < n; ++i) if (cmp(*(begin+i-1), *(begin+i))) return 0;
return -1;
}
#endif
} else {
if (has_asc) {
for (ptrdiff_t i = 32; i < n; ++i) if (cmp(*(begin+i), *(begin+i-1))) return 0;
return 1;
} else {
for (ptrdiff_t i = 32; i < n; ++i) if (cmp(*(begin+i-1), *(begin+i))) return 0;
return -1;
}
}
}
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 <= (ptrdiff_t)INSERTION_SORT_THRESHOLD) {
insertion_sort(begin, end, cmp);
return;
}
constexpr bool is_arith = std::is_arithmetic_v<V>;
constexpr bool is_int = std::is_integral_v<V>;
constexpr bool use_simd =
std::is_pointer_v<Iter> &&
std::is_same_v<std::remove_cv_t<V>, int32_t> &&
std::is_same_v<std::decay_t<Compare>, default_less<int32_t>>;
int order = fast_detect_order(begin, end, cmp);
if (order == 2) return;
if (order == 1) return;
if (order == -1) { reverse_iter(begin, end); return; }
if (handle_partial_ordered(begin, end, cmp)) return;
V min_val{}, max_val{};
if constexpr (is_arith) {
if constexpr (use_simd) {
#if defined(__AVX2__)
minmax_int32_avx2(begin, (size_t)n, min_val, max_val);
#endif
} else {
min_val = *begin;
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;
}
}
}
if constexpr (is_int) {
using wide = std::conditional_t<sizeof(V) < 4, int64_t, V>;
wide range = (wide)max_val - (wide)min_val;
if (range >= 0 && range <= (wide)COUNTING_SORT_RANGE_LIMIT) {
counting_sort_range(begin, end, min_val, max_val);
return;
}
}
size_t m = (size_t)n < SAMPLE_SIZE ? (size_t)n : SAMPLE_SIZE;
V sample[SAMPLE_SIZE];
if (m == (size_t)n) {
for (size_t i2 = 0; i2 < m; ++i2) sample[i2] = begin[i2];
} else {
// 精确采样，避免整数除法的偏差
for (size_t i2 = 0; i2 < m; ++i2) {
size_t idx = (i2 * (size_t)n) / m;
if (idx >= (size_t)n) idx = (size_t)n - 1;
sample[i2] = begin[idx];
}
}
insertion_sort(sample, sample + m, cmp);
size_t k = compute_k_adaptive<V>((size_t)n, sample, m);
if constexpr (is_arith) {
uint64_t recip = 0;
int64_t base_int = 0;
double scale_f = 0.0;
double min_d = 0.0;
if constexpr (is_int) {
base_int = (int64_t)min_val;
int64_t range_i = (int64_t)max_val - base_int;
if (QNQ_UNLIKELY(range_i <= 0)) { insertion_sort(begin, end, cmp); return; }
recip = ((uint64_t)MAX_BUCKETS << 32) / (uint64_t)range_i;
if (QNQ_UNLIKELY(recip == 0)) recip = 1;
scale_f = MAX_BUCKETS_F / (double)range_i;
min_d = (double)base_int;
} else {
min_d = (double)min_val;
double range = (double)max_val - min_d;
if (QNQ_UNLIKELY(range <= 0.0)) { insertion_sort(begin, end, cmp); return; }
scale_f = MAX_BUCKETS_F / range;
}
uint16_t table[MAX_BUCKETS];
build_table<V>(table, k, m, sample, min_d, (double)max_val);
static temp_buffer<uint16_t> bucket_buf;
bucket_buf.resize((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));
const bool dual_hist = ((size_t)n >= DUAL_HIST_THRESHOLD);
uint32_t* histB = nullptr;
if (dual_hist) {
histB = static_cast<uint32_t*>(__builtin_alloca(k * sizeof(uint32_t)));
std::memset(histB, 0, k * sizeof(uint32_t));
}
ptrdiff_t i2 = 0;
if constexpr (use_simd) {
#if defined(__AVX2__)
if ((size_t)n >= SIMD_BUCKET_THRESHOLD) {
i2 = (ptrdiff_t)simd_bucket_int32(
begin, (size_t)n, 0,
(double)min_val, scale_f,
table, bucket_cache, hist, histB);
}
#endif
}
if constexpr (is_int) {
const int64_t base = base_int;
const uint64_t r = recip;
if (dual_hist) {
for (; i2 + 4 <= n; i2 += 4) {
QNQ_PREFETCH(&*(begin + i2 + PREFETCH_DIST));
uint16_t b0 = table[int_bucket((uint64_t)((int64_t)*(begin + i2) - base), r)];
uint16_t b1 = table[int_bucket((uint64_t)((int64_t)*(begin + i2 + 1) - base), r)];
uint16_t b2 = table[int_bucket((uint64_t)((int64_t)*(begin + i2 + 2) - base), r)];
uint16_t b3 = table[int_bucket((uint64_t)((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]; ++histB[b1]; ++hist[b2]; ++histB[b3];
}
for (; i2 < n; ++i2) {
uint16_t b = table[int_bucket((uint64_t)((int64_t)*(begin + i2) - base), r)];
bucket_cache[i2] = b;
++hist[b];
}
} else {
for (; i2 + 4 <= n; i2 += 4) {
QNQ_PREFETCH(&*(begin + i2 + PREFETCH_DIST));
uint16_t b0 = table[int_bucket((uint64_t)((int64_t)*(begin + i2) - base), r)];
uint16_t b1 = table[int_bucket((uint64_t)((int64_t)*(begin + i2 + 1) - base), r)];
uint16_t b2 = table[int_bucket((uint64_t)((int64_t)*(begin + i2 + 2) - base), r)];
uint16_t b3 = table[int_bucket((uint64_t)((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((uint64_t)((int64_t)*(begin + i2) - base), r)];
bucket_cache[i2] = b;
++hist[b];
}
}
} else {
if (dual_hist) {
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]; ++histB[b1]; ++hist[b2]; ++histB[b3];
}
for (; i2 < n; ++i2) {
uint16_t b = table[float_bucket(*(begin + i2), min_val, scale_f)];
bucket_cache[i2] = b;
++hist[b];
}
} else {
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];
}
}
}
if (dual_hist) {
for (size_t j = 0; j < k; ++j) hist[j] += histB[j];
}
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((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));
}
if constexpr (std::is_pointer_v<Iter> && std::is_trivially_copyable_v<V>) {
std::memcpy((void*)&*begin, tmp, (size_t)n * sizeof(V));
} else {
for (ptrdiff_t j = 0; j < n; ++j) begin[j] = tmp[j];
}
if constexpr (!std::is_trivially_destructible_v<V>) {
for (ptrdiff_t j = 0; j < n; ++j) tmp[j].~V();
}
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;
if (cnt <= SMALL_BUCKET_THRESHOLD) {
insertion_sort(sub_begin, sub_end, cmp);
continue;
}
zsort_rec(sub_begin, sub_end, cmp);
}
return;
}
// 非算术类型
{
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((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] = (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((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));
}
if constexpr (std::is_pointer_v<Iter> && std::is_trivially_copyable_v<V>) {
std::memcpy((void*)&*begin, tmp, (size_t)n * sizeof(V));
} else {
for (ptrdiff_t j = 0; j < n; ++j) begin[j] = tmp[j];
}
if constexpr (!std::is_trivially_destructible_v<V>) {
for (ptrdiff_t j = 0; j < n; ++j) tmp[j].~V();
}
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;
if (cnt <= SMALL_BUCKET_THRESHOLD) {
insertion_sort(sub_begin, sub_end, cmp);
continue;
}
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 <= (ptrdiff_t)INSERTION_SORT_THRESHOLD)) {
insertion_sort(begin, end, cmp);
return;
}
zsort_rec(begin, end, cmp);
}
} // namespace qnq
#endif // QNQ_ALGORITHM_H
void sort (unsigned* a, int n) { qnq::sort(a, a + n); }
| Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |