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

Re:Nearly all binary search and merge sort implementations a... by bad_user on Monday January 30, 2012 @04:22PM (#3530699)

Actually most bugs are being introduced in the translation between pseudocode and your working programming language. For instance pseudocode does not deal with 32-bit integers that can overflow.

But that's not the fault of the algorithm, or the fault of its proof and it also has nothing to do with the origin of your computer parts.

Also, the "mechanics" of binary search work perfectly in practice. I see no evidence to the contrary, either in your comment or in the above article and that same implementation described works perfectly in Python.

[ Parent | on HN ]

Re:Nearly all binary search and merge sort implementations a... by arundelo on Tuesday January 31, 2012 @01:34AM (#3532134)

Upvoted for the first two paragraphs, but I can't make sense of the second sentence of the third paragraph. The algorithm given in the article works in Python because Python has different overflow behavior than Java, C, or C++. When you say you "see no evidence", it seems like you are saying the implementation given in the article does work in Java etc.

[ Parent | on HN ]

Re:Nearly all binary search and merge sort implementations a... by nknight on Tuesday January 31, 2012 @02:52AM (#3532303)

Technically, the naïve implementation is perfectly fine for C/C++, so long as size_t is at least 268 bits long on your platform. :)

[ Parent | on HN ]