This link got me the paper in PDF form with absolutely no hassle: http://web.eecs.utk.edu/~langston/courses/cs594-fall2003/HL....
(Appears to be the faculty web site of one of the paper's authors.)
A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
21–30 of 33 posts
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#22This link got me the paper in PDF form with absolutely no hassle: http://web.eecs.utk.edu/~langston/courses/cs594-fall2003/HL.... (Appears to be the faculty web site of one of the paper's authors.)
Thanks for the link. For me, the article really didn't even exist since it wasn't freely available from the ACM site.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#23Please do not submit articles behing pay walls.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#24Perhaps very few know of it because it's hidden behind a ridiculous pay wall.
Sorry about the pay-wall link guys :-( I'm in university so I didn't realize it was this way.
I've posted 3 other links which should allow free access to the paper. I think these things should be open (and free) to start off with.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#25Earlier quoted context omitted.
I agree. I too keep wondering "why?"
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?
I 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".
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#26Perhaps very few know of it because it's hidden behind a ridiculous pay wall.
Sorry about the pay-wall link guys :-( I'm in university so I didn't realize it was this way. I've posted 3 other links which should allow free access to the paper. I think these things should be open (and free) to start off with.
This is precisely what is wrong with the Paywall -- people in the Uni don't know it is there.
Donald Knuth embarassed himself a few years ago when he told people that the library at the Uni was worthless because he can just sit as his computer and view all the literature for free.
Academics generally don't realize that the library at their Uni cuts a million dollar check to Elsevier every year, in addition to a number of other publishers. As a result, they don't see that there is any problem.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#27Earlier quoted context omitted.
Sorry about the pay-wall link guys :-( I'm in university so I didn't realize it was this way. I've posted 3 other links which should allow free access to the paper. I think these things should be open (and free) to start off with.
This is precisely what is wrong with the Paywall -- people in the Uni don't know it is there. Donald Knuth embarassed himself a few years ago when he told people that the library at the Uni was worthless because he can just sit as his computer and view all the literature for free. Academics generally don't realize that the library at their Uni cuts a million dollar check to Elsevier every year, in addition to a numbe…
The other problem is that it cuts academics off from the rest of the world. Because paywalls effectively prevent non-academics from seeing what academics are doing, they end up being underappreciated, and their contributions end up being underutilized. And, since we might as well bring it back to money, I suspect it ultimately has a downward influence on the amount of money legislatures earmark for universities and research.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#28Earlier quoted context omitted.
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?
I 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".
I 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.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#29Earlier quoted context omitted.
This is precisely what is wrong with the Paywall -- people in the Uni don't know it is there. Donald Knuth embarassed himself a few years ago when he told people that the library at the Uni was worthless because he can just sit as his computer and view all the literature for free. Academics generally don't realize that the library at their Uni cuts a million dollar check to Elsevier every year, in addition to a numbe…
The other problem is that it cuts academics off from the rest of the world. Because paywalls effectively prevent non-academics from seeing what academics are doing, they end up being underappreciated, and their contributions end up being underutilized. And, since we might as well bring it back to money, I suspect it ultimately has a downward influence on the amount of money legislatures earmark for universities and r…
you took the words right out of my mouth!
unfortunately when academics are indifferent about marketing themselves to the wider world, they are the losers in the long term.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#30There's an issue here that I really don't understand: why is this never used? For example, the original C++ STL generally did a heck of a good job at exposing an interface to the 1997 state of the art in general-purpose algorithms. So, the spec for std::stable_sort was aimed at Mergesort: O(n log n) comparisons and O(n) additional space due to the space required by the Stable Merge. HOWEVER , if limited space is avai…
"For the sake of speed and simplicity, our algorithm is not stable." There's your answer. In their defense, the authors do include a footnote to another of their papers adding stability and preserving the asymptotic properties, but admit that it's significantly slower. The answer then becomes, "Because mandating the lower complexity bound would increase the real world costs." It's the same reason the standard only re…
Ah, I didn't catch the lack of stability. Thanks.
OTOH, that does not completely address my difficulties. Because there are fall-back algorithms to consider. And so it seems to me that the slower version of Mergesort that is both stable and in-place, still has practical value.
You mention that fast selection typically uses Quickselect, since the known linear-time selection algorithms have much worse average-case performance. That's true; however, e.g., in Musser's 1997 paper where he introduces Introsort (log-linear-time Quicksort variant), he also recommends doing selection by starting with Quickselect, then switching to a linear-time algorithm if the recursion depth exceeds some threshold. The result is a linear-time algorithm with the same average-case performance as Quickselect.
As far as I know, Musser's idea is the standard selection algorithm in use today. Or if it isn't, then it probably should be. [1]
Similarly, I have no problem with C++ std::stable_sort using linear additional space. But if it can't, then why not fall back to another log-linear-time algorithm, instead of the O(n log n log n) that is allowed for in the standard? This stuff has been known for decades. It wasn't taken into account in the 1998 standard, and it still wasn't taken into account in the 2011 standard. Why not?
I kinda feel like I'm beating a dead horse here ... but in any case, there are still unanswered questions.
[1] EDIT: Checked the C++11 standard again. The spec for std::nth_element has not been updated to reflect Musser's idea; it's still "Complexity: Linear on average." OTOH, the spec for std::sort has been updated. In 1998 it was "Approximately N log N ... comparisons on the average," while in 2011 it was simply "O(N log (N)) ... comparisons."