3 ms·

Wow-- apparently Mergesort can be implemented in-place!?

by lliiffee 14y ago

Scaevolus 14y ago
Yes, but people usually don't since it requires more swap operations and is pretty hard to get correct.
- its_so_on 14y ago
  what, "hard to get correct"? Are we talking about fundamental computer science that literally consists of implementing an algorithm made out of compare and swap/move elements...? I can't imagine any sort algorithm for which it can possibly be legitimate to say it's 'hard to get correct' unless it's in the sentence 'it's hard for a first-year computer science student to get correct.' i mean, what is more traditional and basic than implementing tricky sort algorithms?
  - bazzargh 14y ago
    How about binary search? "When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it,[7] and another study shows that accurate code for it is only found in five out of twenty textbooks.[8] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.[9]" http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues http://en.wikipedia.org/wiki/Binary_search_algorithm#Impleme...
    - morsch 14y ago
      I just learned that Java has an unsigned right shift operator >>> from an article cited as a reference in that Wikipedia section. The article has some more details on the subtleties of binary search. For instance, the 20 year old bug in an algorithm proven to be correct was down to integer ranges: int mid = (low + high)/2; breaks (obviously in retrospect, am I missing something?) for low + high > Integer.MAX_INTEGER It can be replaced by the elegant (but to me, somewhat oblique) int mid = (low + high) >>> 1; http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.de/2006/06/extra-extra-read-a... Also from that page, here's the link to the bug in Sun's tracker, priority 2-High, evaluation: "Can't even compute average of two ints" is pretty embarrassing. http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582
pestaa 14y ago
I had this feeling when we implemented it in school, but couldn't think it through. My teacher told me it is not possible and convinced me to give up.
brianhempel 14y ago
The video is not demonstrating an in-place merge sort. Notice how the sorted pairs suddenly merge. There's another buffer (not included in the visualization) where each merged list is temporarily stored while it is being built up. The sudden merger is when that temporary buffer is copied back into the main list.

Wow-- apparently Mergesort can be implemented in-place!?

Scaevolus 14y ago

Yes, but people usually don't since it requires more swap operations and is pretty hard to get correct.

its_so_on 14y ago
what, "hard to get correct"? Are we talking about fundamental computer science that literally consists of implementing an algorithm made out of compare and swap/move elements...? I can't imagine any sort algorithm for which it can possibly be legitimate to say it's 'hard to get correct' unless it's in the sentence 'it's hard for a first-year computer science student to get correct.' i mean, what is more traditional and basic than implementing tricky sort algorithms?
- bazzargh 14y ago
  How about binary search? "When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it,[7] and another study shows that accurate code for it is only found in five out of twenty textbooks.[8] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.[9]" http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues http://en.wikipedia.org/wiki/Binary_search_algorithm#Impleme...
  - morsch 14y ago
    I just learned that Java has an unsigned right shift operator >>> from an article cited as a reference in that Wikipedia section. The article has some more details on the subtleties of binary search. For instance, the 20 year old bug in an algorithm proven to be correct was down to integer ranges: int mid = (low + high)/2; breaks (obviously in retrospect, am I missing something?) for low + high > Integer.MAX_INTEGER It can be replaced by the elegant (but to me, somewhat oblique) int mid = (low + high) >>> 1; http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.de/2006/06/extra-extra-read-a... Also from that page, here's the link to the bug in Sun's tracker, priority 2-High, evaluation: "Can't even compute average of two ints" is pretty embarrassing. http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582

pestaa 14y ago

I had this feeling when we implemented it in school, but couldn't think it through. My teacher told me it is not possible and convinced me to give up.

brianhempel 14y ago

The video is not demonstrating an in-place merge sort. Notice how the sorted pairs suddenly merge. There's another buffer (not included in the visualization) where each merged list is temporarily stored while it is being built up. The sudden merger is when that temporary buffer is copied back into the main list.