6 ms·
A beautiful algorithm that only a very few know of: In-Place Merge in O(n) time
- petercooper 15y agoBeing behind a paywall isn't helping with its publicity. On the plus side, this reminds me I really do need to sign up for the ACM! :)
- icebraining 15y agoSearching the title returns this: http://akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/Huang88.pdf http://akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artik...
- sold 15y agoI get 404 at this URL but google cache is available.
- dhruvbird 15y agoGoogle Cache Link: https://docs.google.com/viewer?a=v&q=cache:n-YwxuJHeAoJ:akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/Huang88.pdf+&hl=en&gl=us&pid=bl&srcid=ADGEESiDsi1Ltl_rtQp5cG61XBYEycPP8BeHj4dwZBfcD0619C1dA-ZsHL67j3l7by6tUVwr8ePc3NYX7G9dkQMXAwHN1GhSieFJvoEHE-rzLGuhClGvkOQVtE8saAY-OMjmNjSUfpGN&sig=AHIEtbRfUaTf_oNJcc1KHP0KWLHm67xArg https://docs.google.com/viewer?a=v&q=cache:n-YwxuJHeAoJ:...
- icebraining 15y agoMy bad. I've actually clicked the "Quick View" link; the possibility of being unavailable didn't cross my mind.
- deleted 15y ago[deleted]
- petercooper 15y agoMaybe, but it's just another paywall, selling a PDF for $39.95.
- dhruvbird 15y agoDoes this link work? http://www.deepdyve.com/lp/association-for-computing-machinery/practical-in-place-merging-J0UfpJlzNh http://www.deepdyve.com/lp/association-for-computing-machine...
- dhruvbird 15y agoOr you can try this one if neither work: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.1155 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.1...
- snth 15y agoMy usual way around this is to search on scholar.google.com. This usually turns up some free versions. It does in this case.
- pwg 15y agoSome source - with a lot of comments - that claims to implement the algorithm: http://www.keithschwarz.com/interesting/code/?dir=inplace-merge http://www.keithschwarz.com/interesting/code/?dir=inplace-me...
- jemfinch 15y agoThat's the same guy that did the fantastic writeup of Dijkstra's Smoothsort: http://www.keithschwarz.com/smoothsort/ http://www.keithschwarz.com/smoothsort/
- ggchappell 15y agoThere'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.
- dhruvbird 15y agoI agree. I too keep wondering "why?"
- warmfuzzykitten 15y agoI 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.
- 15y ago
- bhickey 15y agoI 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.
- forrestthewoods 15y agoPerhaps very few know of it because it's hidden behind a ridiculous pay wall.
- dhruvbird 15y agoSorry 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.
- PaulHoule 15y agoThis 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.
- bunderbunder 15y agoThe 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.
- PaulHoule 15y agoyou 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.
- sblom 15y agoThis link got me the paper in PDF form with absolutely no hassle: http://web.eecs.utk.edu/~langston/courses/cs594-fall2003/HL.pdf http://web.eecs.utk.edu/~langston/courses/cs594-fall2003/HL.... (Appears to be the faculty web site of one of the paper's authors.)
- yason 15y agoThanks for the link. For me, the article really didn't even exist since it wasn't freely available from the ACM site.
- chmike 15y agoPlease do not submit articles behing pay walls.
- mdonahoe 15y agoCan someone writeup a gist of the algorithm?
- k_l_s 15y agoGiven two sorted lists A and B concatenated as a single list AB: Divide the list up into sqrt(n) pieces, each of size sqrt(n). Create one such piece consisting of the sqrt(n) largest elements of the combined list and move this piece to the left-most position (call this the buffer piece), while the remaining pieces are simply formed from the remaining elements. Note that the remaining pieces will retain their ordering from the fact that A and B were originally sorted (as long as care is taken not to cross the boundary of A/B), while the left-most piece need not be sorted at this point. Stable? [I didn't see it in the paper, but I think it's necessary] sort the sqrt(n)-1 non-leftmost pieces in non-decreasing order by their tail element. Finally, merge (details left out as to when to stop the merge) the longest sequence of pieces constructable from the beginning of the un-merged list so that the tail element of any piece is not greater than the head element of it's downstream piece with this sequence's downstream piece, using the left-most piece as the buffer and swapping the min element of the two lists into the min buffer position instead of overwriting the buffer element. After a merge, the buffer piece will remain as a single piece and may be re-used as the buffer for the next merge. In the end, simply sort the buffer piece. Notice that we may use an O(n^2) sort for the two sorts that we need to perform without breaking the merge's linear time property since in both cases we're sorting sqrt(n) items. The min element of the remaining pieces will always make its way into the min buffer position a sorted lists' pieces will not be re-ordered by the tail-element sort. Anyhow, many details left off, but you asked for a gist and I believe that this qualifies as a gist.