News for hackers. Stuff that matters.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by btilly on Tuesday February 16, 2010 @09:26PM (#1130649)
It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int?

I also question the mergesort assertion. I've implemented mergesort several times, almost always expressed in terms of writing to/from pipes of data (that under the hood eventually wound up going to disk I/O in some way). Those solutions will not suffer from any form of this bug for the simple reason that you never access anything by index.

The curious might wonder why I felt a need to implement such a well-known algorithm myself. Well in addition to the times I did it for fun, one time I had a large dataset to process that had already broken the database, and the computer I had to process it with didn't have enough disk space for the whole dataset. So I needed to do a mergesort while keeping all data that hit disk in compressed form...

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by wvenable on Tuesday February 16, 2010 @10:28PM (#1130758)
> What happens when you have an array with more elements than can be expressed by an int?

You probably couldn't have an array that big and even if you could, it's likely this function would accept it at compile time. The problem here is that you're passing it an array that it is advertised to handle, yet it fails.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Groxx on Wednesday February 17, 2010 @01:08AM (#1130986)
It's pretty easy, actually.

Make two arrays, and have the end of one act like a linked list to the start of the second. When a [x] value is larger than the size of the first, just subtract the first's size from x, and find that value in the second. It's even still O(1) time.

Viola, you've now got nearly double the storage of what you can reference, and it'll work in a generic case, but you'll never be able to refer to anything larger than your index-number can reach.

To make matters worse, do you know if your library isn't doing this for you? It'd allow you to extend your array without having to copy the whole thing, which saves a LOT of time on frequently-lengthening arrays. The extremely small cost of checking an int's size before actually accessing the sub-array necessary is often negligible compared to duplicating potentially billions of values.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by jedbrown on Wednesday February 17, 2010 @07:36AM (#1131383)
It's not at all uncommon to have an array that big these days. But the API should use size_t for the array size (or whatever is available in your language of choice).
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by InclinedPlane on Wednesday February 17, 2010 @06:28AM (#1131320)
The difference is that the constraint of using a signed int as the length of the array is known and available to users of the function. What happens when you try to do that is you get a compiler error, because it won't implicitly cast from, say, bigint or unsigned int down to signed int, for example. That's not necessarily a defect, that's just a constraint.

This contrasts with the overflow defect which would cause the mergesort routine to fail when given an otherwise perfectly valid input.

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by sparky on Tuesday February 16, 2010 @10:35PM (#1130772)
It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int?

I don't think you can do that in Java. In the more general case, you're right, but I think you can solve it by just using a long long or whatever your language has instead of an int for the appropriate calculations.