[AlEinstein]

Is this cache friendly on a modern cpu? On the face of it, it seems to be quite cache unfriendly.

[daniel-cussen]

I was surprised to find that it is, especially if the data is clustered. What ends up happening is the elements near the top of the bracket get cached so they can usually be accessed quickly.

Note that if your data is uniformly randomly distributed the caching will hurt and it will be slower than quicksort, as this is quicksort's optimal use case.