Wow-- apparently Mergesort can be implemented in-place!?
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?
"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#Impleme...
int mid = (low + high)/2;
low + high > Integer.MAX_INTEGER
int mid = (low + high) >>> 1;
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.
My teacher told me it is not possible and convinced me to give up.