My favorite artistic illustration is probably Jorge Stolfi's drawing inspired by the self-adjusting splay tree data structure of Sleator and Tarjan:
https://www.link.cs.cmu.edu/splay/tree5.jpg
There's an important distinction that your explanation glosses over, which is that MergeSort is an out-of-place sort while QuickSort is in-place. As a practical matter, this distinction is important and it makes the two algorithms not quite duals. Your explanation of why we can assume that QuickSort pivots are medians makes sense, but it also glosses over one of the deep insights about why QuickSort works at all, which is that with unsorted data, the choice of pivot will rarely be bad (it will be "near the middle on average.")
Yes, this efficiency-aspect is not captured in the illustration -- while splitting perfectly _by index_ comes for free, splitting perfectly _by value_ needs nontrivial work (median-finding).
Yes and with naïve median-finding comes pathological inputs that hit the worst case O(n^2). Something to watch out for if you’re sorting user-provided input as that could open you up to some silly denial of service attacks!
Socrates supposedly loved going to the market. When his students asked him about this, Socrates replied, "I love to go and see all the things I am happy without." :)
Maybe it has to do with symmetries. The proportion of symmetric polys in successive generations goes towards zero. I suspect that this 'pollutes' the asymptot.
About published research, I just glanced at the little I found, (as I often can't do more than glance, being limited in Maths.)
"Seeing an astronomer using a telescope to observe a galaxy, no-one will confuse the telescope with the galaxy. Mathematics differs from science in that there is no clear distinction between the tools and the objects of study." -- D.Aldous
I don't think there's a difference here between Science and Mathematics. Scientists also study their tools (e.g. telescopes are studied by Optics), and use the objects of their studies as tools (e.g. galaxies can be used as telescopes, see: https://en.wikipedia.org/wiki/Gravitational_lens).
Edited to add:
The author of the quote tried to find an example that evokes vivid imagery, and also very extreme: it's obviously absurd to confuse a telescope with a galaxy, thinks the layman. While this turns out to be literally false, the point of the quote may still stand. The discipline that studies the real tools of Science is not Science itself, but the Philosophy of Science. This shouldn't be like this, and it wasn't until lately. Philosophy and Science used to be one and the same, but around a hundred years ago they separated, and this hurt both tremendously, in my opinion.
You are right in general, but when the quote is from someone on whose research the result builds in an important way (as it is the case here), I would say it is fair.
Your first point is correct, but just to clarify your second point, these two definitions are not quite equivalent, as there is a world of functions growing more quickly than log^k(n) no matter how large constant k, but still within n^o(1).
For an example, consider 2^sqrt(log(n)).
This is a bit similar to something being faster than polynomial, but slower than exponential.
Thanks for the clarification! I didn't mean to say the two definitions were equivalent, as indeed they aren't. Rephrasing my second point to (hopefully) eliminate the ambiguity: There are two non-equivalent popular definitions for "almost linear" or "nearly linear" (n^(1+o(1)) and O(n log^k(n)), and nevertheless classifying "n log^1000 n" as almost linear is uncontroversial in the sense that both of the common definitions do it.
(The second paragraph of my original message addressed a point made in the parent's second paragraph, which has since been edited out.)
There are multiple long standing "Project 0" efforts in the US that aim to get pedestrian fatalities down to 0.
They have a range of goals including reducing Urban speed limits to 20-25mph and adding more safety features to cars.
Sad fact is modern giant SUVs have very poor rear visibility and children are just not visible if they are behind the vehicle. Backup cameras are the only reasonable option aside from "stop driving obscenely oversized vehicles."
(Another solution would be changing current laws so that 3 row station wagons were legal again, right now SUVs and Minivans fill a need that the 3 row station wagon used to, but it was legislated away long ago.)
I imagine this organization and similar orgs. It would be interesting to see if the new legislation has helped decrease the number of backover accidents.
This appears to be an example of technology solving a design flaw rather than rent-seeking capitalism.
There are a good reasons why we don't usually do average-case analysis of algorithms, chief among them that we have no idea how inputs are distributed (another reason is computational difficulty). Worst-case bounds are pessimistic, but they hold.
In CS you're often dealing with adversarial inputs, for which worst-case analysis is obviously the right approach. Not sure that there's anything comparable to that in most statistical settings.
Honest question: who does it harm? These aspects that you mention may not be to your (or to my) taste, but if they are relatively harmless and the other stuff is overwhelmingly good, why not let it go?
Fundamentally, the ritualistic behavior harms belief in science. Doing things because we believe in magic of any kind is fostering belief in other magic - for example healing by similar magic, the roots for both go back to Rudolf Steiner.
