>I conjecture that it actually gets mergesort down to a real O(N log N) instead of the O(N log N log N) of the usual mergesorts.
I don't think it does in the worst case. I'd bet money you could construct an adversarial input that would force you to look at more of each key than you'd have to in order to get down to "real" O(n log n).
>MIX in particular had 5-character memory words, but only 4000 words of memory, so its comparison time for internal sorting is quite precisely constant for any realistic data.
If we're being precise here, then it is certainly bounded above by a constant. But, this is also the same sense in which there is literally no such thing as a Turing machine (all physical machines, even one the size of the universe, are linear bounded automata, at best).
> Anyway, back to the issue at hand: assembly language exposes all the computational costs by default, which is what you want if you're going to prove theorems about them, while high-level languages obscure them by default, so more of your theorems will be incorrect. And that's Knuth's primary concern.
Except, no, you don't. Both you and I just got through explaining why.
> That level of single-minded pursuit of excellence is the reason we can learn things from books Knuth wrote in the 1960s that are still useful for programming computers that are literally a billion times bigger than the machines Knuth used as his model. It's also the reason he's not done yet, 55 years later, with what he thought would be a single book, done in a year or two.
No, it most certainly is not. I'm assuming you've read at least some of TAOCP. Knuth certainly introduced some mathematics and techniques for the analysis of algorithms in TAOCP, but literally none of the algorithms themselves were first published there. This is not a research monograph. It's a reference. The algorithms themselves were published and proven, including runtimes, before they ever made it into those pages.
And, yes, there is plenty that almost anyone can learn from these books and the subsequent fascicles, but it's nothing to do with the computational model. Not one result in TAOCP contradicts the previously published work. We can learn from it because there is simply so much there to learn from. There's a reason that when Steve Jobs told Don Knuth "I've read all your books," Knuth responded that jobs was "full of shit." [0]
I don't think it does in the worst case. I'd bet money you could construct an adversarial input that would force you to look at more of each key than you'd have to in order to get down to "real" O(n log n).
>MIX in particular had 5-character memory words, but only 4000 words of memory, so its comparison time for internal sorting is quite precisely constant for any realistic data.
If we're being precise here, then it is certainly bounded above by a constant. But, this is also the same sense in which there is literally no such thing as a Turing machine (all physical machines, even one the size of the universe, are linear bounded automata, at best).
> Anyway, back to the issue at hand: assembly language exposes all the computational costs by default, which is what you want if you're going to prove theorems about them, while high-level languages obscure them by default, so more of your theorems will be incorrect. And that's Knuth's primary concern.
Except, no, you don't. Both you and I just got through explaining why.
> That level of single-minded pursuit of excellence is the reason we can learn things from books Knuth wrote in the 1960s that are still useful for programming computers that are literally a billion times bigger than the machines Knuth used as his model. It's also the reason he's not done yet, 55 years later, with what he thought would be a single book, done in a year or two.
No, it most certainly is not. I'm assuming you've read at least some of TAOCP. Knuth certainly introduced some mathematics and techniques for the analysis of algorithms in TAOCP, but literally none of the algorithms themselves were first published there. This is not a research monograph. It's a reference. The algorithms themselves were published and proven, including runtimes, before they ever made it into those pages.
And, yes, there is plenty that almost anyone can learn from these books and the subsequent fascicles, but it's nothing to do with the computational model. Not one result in TAOCP contradicts the previously published work. We can learn from it because there is simply so much there to learn from. There's a reason that when Steve Jobs told Don Knuth "I've read all your books," Knuth responded that jobs was "full of shit." [0]
---
[0]:https://www.folklore.org/StoryView.py?project=Macintosh&stor...