Vaughan

Interesting bug in sort algorithm (not FMP)

Discussion created by Vaughan on Jan 30, 2012
Latest reply on Jan 31, 2012 by mbraendle

I just read this article talking about a bug in sort algorithm that has been dormant for 50 years:

 

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

 

TL;DR -- the bug is in this line of code:

 

int mid = (low + high) / 2;

 

...which "sets m to the average of l and u, truncated down to the nearest integer." The bug occurs when the sum of (low + high) is greater than the maximum positive int value (231 - 1).

 

As data sets get bigger and bigger these kinds of errors are going to crop up more frequently.

Outcomes