I just assumed Einstein-tier people had discovered all the optimal ways to do things by now.
Do you have a process for coming up with these improved algorithms, or does it just start from a passing thought in your mind?
And that's ignoring that "optimal" is a shifting target. What's optimal on a 1960s computer where RAM is as fast as registers may not be optimal on a modern CPU with instruction-level parallelism and RAM that's orders of magnitude slower than registers.
The worst part is that most people pursuing a computer science degree actually want to learn about software engineering, so most curricula nowadays disappoint both the people that want to become software engineers ("why do I have to learn about formal grammar automata") and those that want to become computational mathematicians ("why do I have to do a course on agile?").
But I can say that mathematics is an ancient "science" which has been studied by great scholars for millennia, but many of the things we take for granted today are relatively recent: modern set theory was introduced 150 years ago by Cantor and Dedekind, meaning things like Russel's Paradox [1], Gödel's Incompleteness Theorem [2] and the Peano Axioms [3] have all been discovered after that, despite being taught in many (university-level) introductory math courses today. Rings are also relatively young [4]. In comparison, imaginary numbers are about 500 years old.
1: https://brilliant.org/wiki/russells-paradox/
2: https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
An easy way to reconcile this is to consider that everything is an engine (~ 'system that transforms energy'); and likewise that everything is a computer (~ a 'system that turns inputs to outputs'). Each field offers a different perspective, on different aspects of, the world :)
If anything I think he missed a key component which is that algorithmic improvement is actually only interesting in a few very specific places.
I think pdqsort actually shows this to be true - it uses added complexity to improve on things that really do fit in a few lines of pseudocode.
> An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms
Spoiler alert, the "algorithm M" is a brute-force search; the "low-order additive terms" in its time complexity come from brute-force searching for provably faster programs; if one is found, we restart with that. All the time spent searching for proofs is independent of the input size (e.g. it depends on "sorting", but not which particular list we've been given); hence it's technically just a constant 'warmup time'!
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.
This is the answer to your question, almost everyone makes the same assumption you do.
There are a surprising number of problems in computer science that no one works on because everyone assumes that other clever people are. Relatedly, people assume the set of possible solutions has been exhaustively explored because there have been no incremental improvements in decades. Or people assume the scope of optimality of a well-known solution is much broader than it actually is.
The vast majority of people in software never test or revisit these assumptions. If you do test these assumptions, you will be surprised by how often you find low-hanging fruit.