Nearly all binary search and merge sort implementations are broken (2006)

It is not sufficient merely to prove a program correct; you have to test it too. Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible. This statement is tantamount to saying "you don't merely need to prove Fermat's Last Theorem, you also have to test it for all possible input values". By this line of reasoning, most of mathematics should be thrown out. If…

It's not binary searches and merge sorts that are broken, it's the INT data type that is "broken" (and I put "broken" in scare quotes because they aren't really broken, they just don't do what you want in most cases). People tacitly assume that INTs model the integers, but they don't. They model the integers modulo 2^N for some value of N. If you code as if INTs were integers and you hit the 2^N limit you will lose. The…

Not just binary search. Anything that involves addition of signed integers could overflow.

I remember when this came out. I looked at the code for Binary Search & Merge Sort that I had written for a Data Structures and Algorithms class I was teaching at the time. Neither of these had the bug. The reason was that I was using C++ iterators. template<typename RAIter> void mergeSort(RAIter first, RAiter last); So I could not do RAIter middle = (first + last) / 2; because the there is no operator+ on iterators in general. Instead…