All the time in my experience. This is why radix sort is so useful. Many key types can be packed into 64 bits in a way that's compatible with the bitwise lexicographic ordering. You can pack 9-character low ASCII strings (or 10-character [a-zA-Z_][a-zA-Z0-9_]* identifiers) in 64 bits. [1] You can even do sub-bit packing, e.g. c + 3 * b + 3 * 7 * a for the tuple (a, b, c) with lexicographic ordering where 0 <= c < 3 and 0 <= b < 7. If you wanted to sort ascending on a and c but descending on b you'd replace b by 6 - b in the embedding. For radix sort you can also support 2's complement integers and IEEE-754 floats by simple key transformations. You get the idea: many complex keys are efficiently reducible to machine integers.
My default algorithm for scalar sorting is usually an optimized LSD radix sort. It's inherently branchless; its downside compared to quicksort is worse cache locality for the scattered writes after the histogram phase. Incidentally, quicksort is closely related to MSD radix sort with radix 2, which effectively partitions using data-independent pivots.
[1] For longer strings you would sort on the prefix using this embedding and then do a final pass where you sort among each (hopefully small) set of prefix-colliding strings by a different method, e.g. insertion sort for small sets.
> Combining these two tricks could lead to merge sort on par with the simple partition loop of QuickSort. However it’s just a mitigation. If instead of sorting a simple primitive value we would sort pointers to a struct. The comparison operator would have an extra load which immediately adds to the critical path. QuickSort is immune to this, even rather costly comparisons do not influence the ability to make progress. Of course if the comparison itself suffers from frequent branch misses, then that will limit the ability to overlap different stages of the iteration in the CPU pipeline.
In the benchmark code for the blog, he includes a benchmark that has indirection to illustrate this, though these results were not included in the article itself. On my machine I get:
$ CC=clang bazel build -c opt :all
$ bazel-bin/bench_sort --benchmark_filter=BM_IndirectionSort
-------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------------------
BM_IndirectionSort<1, std_sort> 64 ns 64 ns 10900000
BM_IndirectionSort<1, std_stable_sort> 89 ns 89 ns 7900000
BM_IndirectionSort<1, std_heap_sort> 112 ns 112 ns 6300000
BM_IndirectionSort<1, exp_gerbens::QuickSort> 26 ns 26 ns 27000000
BM_IndirectionSort<1, HeapSort> 96 ns 96 ns 7300000
BM_IndirectionMergeSort<1> 45 ns 45 ns 15500000 BM_IndirectionSort<1, std_sort> 93 ns 93 ns 7700000
BM_IndirectionSort<1, std_stable_sort> 126 ns 125 ns 5600000
BM_IndirectionSort<1, std_heap_sort> 172 ns 172 ns 4200000
BM_IndirectionSort<1, exp_gerbens::QuickSort> 34 ns 34 ns 19000000
BM_IndirectionSort<1, HeapSort> 157 ns 157 ns 4700000
BM_IndirectionMergeSort<1> 68 ns 68 ns 10400000
BM_IndirectionSort<0, std_sort> 74 ns 74 ns 9500000
BM_IndirectionSort<0, std_stable_sort> 91 ns 91 ns 7800000
BM_IndirectionSort<0, std_heap_sort> 125 ns 125 ns 5800000
BM_IndirectionSort<0, exp_gerbens::QuickSort> 26 ns 26 ns 27200000
BM_IndirectionSort<0, HeapSort> 77 ns 77 ns 9300000
BM_IndirectionMergeSort<0> 36 ns 36 ns 19400000In such a system, sorting the two sets of IDs allows you to implement an O(N) or O(M log N) algorithm depending on the relative sizes of the two sets. If one set is much smaller than the other, then you can just iterate the smaller set and binary search the larger set. If the two sets are comparable in size you can walk a cursor in each.
These IDs are probably small -- 32 bits will generally do. That's a "pure scalar type that is native to the machine".
Mind you, these are smallish arrays in practice. Typically you might see users with a few hundred group memberships and access controls with a few tens of grants. But you might have many users, and many access controls, so many sorts to perform.
Build hash table in O(N) of the smaller set, then probe M entries of the larger in the table.
If we rely on sorted order, we can make it a requirement/invariant that these sets are maintained in sorted order. Membership in a group rarely changes; if a user is added to a new group, that can be inserted in order. A binary heap structure could be used to keep these objects in array form, while allowing better than linear insertion.
Usually you're sorting pointers to objects, and there is some indirection required to compare them (perhaps an outright call through a function pointer).
Here is one good application: ordering an array of pointers by increasing address. That doesn't require indirection upon them, and is useful: e.g. if these are pointers into a heap we wish to compact.