faster string sorting with long common prefix?

algorithm, data-structures, sorting, string

Solution

At last I found a Ternary Quick Sort works well. I found the algorithm at www.larsson.dogma.net/qsufsort.c.

Here is my modified implementation, with similar interface to std::sort. It's about 40% faster than std::sort on my machine and dataset.

#include <iterator>

template<class RandIt> static inline void multiway_qsort(RandIt beg, RandIt end, size_t depth = 0, size_t step_len = 6) {
    if(beg + 1 >= end) {
        return;
    }

    struct { /* implement bounded comparing */
        inline int operator() (
                const typename std::iterator_traits<RandIt>::value_type& a,
                const typename std::iterator_traits<RandIt>::value_type& b, size_t depth, size_t step_len) {

            for(size_t i = 0; i < step_len; i++) {
                if(a[depth + i] == b[depth + i] && a[depth + i] == 0) return 0;
                if(a[depth + i] <  b[depth + i]) return +1;
                if(a[depth + i] >  b[depth + i]) return -1;
            }
            return 0;
        }
    } bounded_cmp;

    RandIt i = beg;
    RandIt j = beg + std::distance(beg, end) / 2;
    RandIt k = end - 1;

    typename std::iterator_traits<RandIt>::value_type key = ( /* median of l,m,r */
            bounded_cmp(*i, *j, depth, step_len) > 0 ?
            (bounded_cmp(*i, *k, depth, step_len) > 0 ? (bounded_cmp(*j, *k, depth, step_len) > 0 ? *j : *k) : *i) :
            (bounded_cmp(*i, *k, depth, step_len) < 0 ? (bounded_cmp(*j, *k, depth, step_len) < 0 ? *j : *k) : *i));

    /* 3-way partition */
    for(j = i; j <= k; ++j) {
        switch(bounded_cmp(*j, key, depth, step_len)) {
            case +1: std::iter_swap(i, j); ++i;      break;
            case -1: std::iter_swap(k, j); --k; --j; break;
        }
    }
    ++k;

    if(beg + 1 < i) multiway_qsort(beg, i, depth, step_len); /* recursively sort [x > pivot] subset */
    if(end + 1 > k) multiway_qsort(k, end, depth, step_len); /* recursively sort [x < pivot] subset */

    /* recursively sort [x == pivot] subset with higher depth */
    if(i < k && (*i)[depth] != 0) {
        multiway_qsort(i, k, depth + step_len, step_len);
    }
    return;
}

Problem

Original source