Function das_stable_index_r

examples/sort/bench_stable_sort.cpp:161–193

template <typename Compare>
inline void das_stable_index_r(void * base, size_t nel, size_t width, Compare cmp) {
    if (nel <= 1) return;
    unsigned char * a = static_cast<unsigned char *>(base);
    std::vector<uint32_t> perm(nel);
    for (uint32_t k = 0; k < uint32_t(nel); k++) perm[k] = k;

    das_qsort_r(perm.data(), nel, sizeof(uint32_t), [&](const void * pa, const void * pb) {
        uint32_t ia = *static_cast<const uint32_t *>(pa);
        uint32_t ib = *static_cast<const uint32_t *>(pb);
        const unsigned char * ea = a + size_t(ia) * width;
        const unsigned char * eb = a + size_t(ib) * width;
        if (cmp(ea, eb)) return true;
        if (cmp(eb, ea)) return false;
        return ia < ib;                                          // unique tiebreak → stable order
    });

    // Apply gather permutation final[k] = orig[perm[k]] in place. Each cycle reads each
    // source exactly once before it is overwritten; orig[k] is parked in tmp.
    std::vector<unsigned char> tmp(width);
    const uint32_t DONE = 0xFFFFFFFFu;
    for (uint32_t k = 0; k < uint32_t(nel); k++) {
        if (perm[k] == DONE || perm[k] == k) { perm[k] = DONE; continue; }
        sized_memcpy(tmp.data(), a + size_t(k)*width, width);    // park orig[k]
        uint32_t cur = k;
        for (;;) {
            uint32_t src = perm[cur];
            if (src == k) { sized_memcpy(a + size_t(cur)*width, tmp.data(), width); perm[cur] = DONE; break; }
            sized_memcpy(a + size_t(cur)*width, a + size_t(src)*width, width);
            perm[cur] = DONE;
            cur = src;
        }
    }
}

// ============================================================================
// Verification — the gold standard. Checks ALL of: