4 ms·
I kind of stopped reading after I learned the algorithm requires O(sqrt(n)) blocks each of O(sqrt(n)) size. Since sqrt(n)*sqrt(n) = n, how is this an improvemen
by warmfuzzykitten 15y ago
I kind of stopped reading after I learned the algorithm requires O(sqrt(n)) blocks each of O(sqrt(n)) size. Since sqrt(n)*sqrt(n) = n, how is this an improvement over the standard technique that simply uses an additional O(n) space?
- jemfinch 15y agoYou misunderstand. The algorithm chunks the existing input into O(sqrt(n)) blocks of O(sqrt(n)) size. That's why they call it an "in place" merge.
- batista 15y agoI kind of stopped reading Seldom is a comment beginning with this insightful. Why stop or "kinda stop", and then criticize? Only criticize if you have read FULLY. Hint: "in place".
- warmfuzzykitten 15y agoI deserved that. Thanks also to jemfinch for more constructively pointing out my error. It happens from time to time: one's mind gets stuck on a detail, in this case a misunderstanding, and starts rejecting, which kills learning dead in its tracks. This all swims in a sea of "half as fast" and "not order-preserving" which further reinforces rejection - after all, if one wanted a non order-preserving in-place sort, there are faster ones. None of this is in any way a criticism of the paper but more a reflection on the state of mind that leads sometimes to being less than insightful.