Musings from The Software Underground

Google just posted to one of their blogs about a bug that was found in most binary sorts, including Merge Sort. Now Merge Sort has been around FOREVER and any computer scientist worth their salt has used it in some capacity, even if it was in the ol' "implement these sorts and compare the performance of each..." assignment.

Apparently Google engineers found a bug in binary sorts, one that has lain dormant for nearly 50 years. Now a typical binary sort is about 17 lines. 17 lines that thousands upon thousands of engineers have used, looked at, written about, etc. and even now a bug can be found in those 17 lines. Crazy, but it explains the adage "there is always one more bug."

The Google post sums it up best this way:

"We programmers need all the help we can get, and we should never assume otherwise. Careful design is great. Testing is great. Formal methods are great. Code reviews are great. Static analysis is great. But none of these things alone are sufficient to eliminate bugs: They will always be with us. A bug can exist for half a century despite our best efforts to exterminate it. We must program carefully, defensively, and remain ever vigilant."

Read the entire post here.