Some source - with a lot of comments - that claims to implement the algorithm:
http://www.keithschwarz.com/interesting/code/?dir=inplace-me...
A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
11–20 of 33 posts
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#12There'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 available, then it is allowed to use O(n log n log n) comparisons, since a slower in-place algorithm is used. [1]
Why? With the algorithm from this article, we can do an O(n log n) in-place Mergesort. I imagine it's not as fast as the standard algorithm that requires O(n) additional space -- although the abstract of this article does call the in-place merge algorithm "reasonably competitive". But it certainly sounds like it would be a better fall-back option.
Similarly, lots of languages have moved toward some version of Mergesort for their standard sorting algorithm: Perl, Python ("Timsort" is a Mergesort variant). Even some versions of the "C" Standard Library's qsort are implemented with Mergesort these days. I never hear about any of these being in-place. But the work in this article isn't exactly a secret.
So: I don't get it.
[1] EDIT: I checked the C++11 spec. It is the same. std::stable_sort does O(n log n) comparisons if sufficient memory is available, and O(n log n log n) if not.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#13There'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…
I agree. I too keep wondering "why?"
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#14There'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…
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?
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#15I came across this paper about five years back. At the time I sent an e-mail to Professor Langston thanking him for his insights and clarity in explaining them. Here's his reply:
Thanks for your kind note Brendan. It's been over
twenty years since we wrote that paper. One never
knows which works will survive the test of time.Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#16There'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…
[deleted]
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#17Perhaps very few know of it because it's hidden behind a ridiculous pay wall.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#18Earlier 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?
You 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.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#19There'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 requires nth_element to be average case linear, rather than worst-case linear; there exist worst-case linear algorithms (like CLR's median of medians algorithm) but their real world performance is far worse than quickselect.
Re: A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
#20Some source - with a lot of comments - that claims to implement the algorithm: http://www.keithschwarz.com/interesting/code/?dir=inplace-me...
That's the same guy that did the fantastic writeup of Dijkstra's Smoothsort: http://www.keithschwarz.com/smoothsort/