<p>The paper <a href="https://arxiv.org/abs/1403.2056" rel="nofollow noreferrer">Engineering Parallel String Sorting</a> has, surprisingly, benchmarks of a large number of single-threaded algorithms on an URL dataset (see page 29).  Rantala's variant of multikey quicksort with caching comes out ahead; you can test multikey_cache8 in <a href="https://github.com/rantala/string-sorting" rel="nofollow noreferrer">this repository cited in the paper</a>.  </p>

<p>I've tested the dataset in that paper, and if it's any indication you're seeing barely one bit of entropy in the first ten characters, and distinguishing prefixes in the 100-character range.  Doing 100 passes of radix sort will thrash the cache with little benefit, eg sorting a million urls means you're looking for ~20 distinguishing bits in each key at a cost of ~100 cache misses.</p>

<p>While in general radix sort will not perform well on long strings , the optimizations that Kärkkäinen and Rantala describe in <a href="https://link.springer.com/chapter/10.1007%2F978-3-540-89097-3_3" rel="nofollow noreferrer">Engineering Radix Sort for Strings</a> are sufficient for the URL dataset.  In particular they read ahead 8 characters and cache them with the string pointers; sorting on these cached values yields enough entropy to get past the cache-miss problem.</p>

<p>For longer strings try some of the LCP-based algorithms in that repository; in my experience the URL dataset is about at the break-even point between highly-optimized radix-type sorts and LCP-based algorithms which do asymptotically better on longer strings.  </p>
faster string sorting with long common prefix?
<p>I have a set of strings. 90% of them are URLs start with <code>"http://www."</code>. I want to sort them alphabetically.</p>

<p>Currently I use C++ std::sort(). but std::sort is a variant of quick-sort based on comparison, and comparing two strings with long common prefix is not effecient. However (I think) a radix-sort won't work either, since most strings are put in the same bucket because of long common prefix.</p>

<p>Is there any better algorithm than normal quick-sort/radix-sort for this problem?</p>