> How is it that programmers are still discovering state-of-the-art algorithms? I just assumed Einstein-tier people had discovered all the optimal ways to do th

> How is it that programmers are still discovering state-of-the-art algorithms? I just assumed Einstein-tier people had discovered all the optimal ways to do things by now. Because it's a moving target. There isn't a fixed 'optimal' sorting algorithm. We've had worst case O(n log n) sorting algorithms for decades, since at least the '50s, possibly the '40s. pdqsort isn't more 'optimal' in the algorithmic sense than merge sort is, they're both worst/expected O(n log n) algorithms. If RAM is low-latency and your CPU isn't super scalar, heapsort is going to take less time than quicksort. With high-latency RAM and speculative executing CPUs, quicksort is going to take less time than heapsort. So every few hardware generations we need to sit down and benchmark everything. pdqsort is based on the principal that the real world is different than the academic world. There are no frictionless spherical cows in a vacuum. In academic research, we assume that the data has been contrived to break your algorithm, or it's randomly distributed. In the real world, data is almost never randomly distributed. A lot of data that gets plugged into your standard library of choice's sorting algorithm is already sorted. Or is sorted in reversed. Or is sorted with one random element plopped onto the end. Or is sorted with one element randomly in the middle that's out of place. pdqsort is designed to account for that.