In modern computers locality is usually the biggest factor if you want speed. A lot of sorting algorithms that might have the same algorithmic complexity can ha

In modern computers locality is usually the biggest factor if you want speed. A lot of sorting algorithms that might have the same algorithmic complexity can have different locality properties. If you think about quicksort, it partitions everything starting from the coarsest level, so the locality increases as it goes along. There are likely a lot of unexplored sorting algorithms that use statistics gathering to at least increase locality faster by placing items closer to their final place sooner. If you think about an array of numbers, you can gather a distribution first and try to place numbers where they would end up according to the distribution to get them much closer to their final position than an initial partition. That would mean running through the array once first, but because of prefetching, that would be much faster than accessing elements by skipping around.