Nearly All Binary Searches and Mergesorts Are Broken

> (2006)

In the very least,this should feature in the title. In fact, previous submissions from over a decade ago also feature year in the title.

Otherwise it conveys the idea that this is some major epiphany.

It was certainly possible to run the algorithm on 16GB of array before the moment when it happened but did the original developer have that sort of space on their desktop at the time? Possibly not.

If a unit test only runs on a server and not on the laptops of the developers then its not going to be written, whereas ideally someone should write a test that is tagged to only run on the server but that is a lot of extra work if that isn't a common thing on a project. Even now I would be quite wary of producing a max size input test for an array of ints and especially objects, that is going to raise some questions due to being a slow test and a highly resource consuming one.

If I was worrying about the same in aerospace programming however then no question that test would get written and we would ensure it got run on the hardware that it was designed to run on. In typical business software its less common to run potentially very long running tests and simulations of the machines states everyone wants to go faster than that especially for the sake of a max input test.

Are you quantizing information?

> certain scale

Make it explicit. If the array is too large, throw an IllegalArgumentException. Document the limit. Then I agree with you.

Otherwise, if an allowed input crashes the program at runtime with a random exception, I respectfully disagree.

The problem is that it's not that much harder to make it work for all the valid inputs.

Not doing that is not good enough.

Another example is summing lots of floats naively instead of using Kahan's algorithm.

It's like we had a theory of gravity that doesn't work on Mars because we have unnecessary division by (m-Mars' mass) in our laws :) It wouldn't be good physics.

I would disagree. The inputs to these functions are user controlled and so can be forced to break, whereas humans cannot change how gravity works.

I'm not a Java programmer, but how would you load of a 1GB file into memory? I assume read returns some kind of an array.

Also big arrays being (supposedly) a coffeee smell doesn't mean that code handling them improperly is not buggy.

Relational databases often require searching and sorting gigabytes of data to answer queries (sometimes larger than RAM if e.g. k-way merge sort is used) so it doesn't seem that far-fetched, especially given that there are database systems written in Java.

I often think AI is mostly crap, wasting a lot of energy for very questionable benefits. But could/should this repetitive task of reminding submitters to follow the submission guidelines and add the year to submissions of old articles be automated?

The difference is that we know for a fact that the proper implementation works for integers up to 2^31, whereas the improper implementation deceived us into thinking that the code would work in situations where the code actually doesn't work.

I find it valuable to understand when my code will crash.

Article was written in 2006 when 32-bit architectures were dominant.

I suppose the issue is moot now on 64-bit architectures, as the difference between 2^62 and 2^63 isn't relevant. (2^62 bytes is 4611686 terrabytes.)

The use of:

   int high = a.length - 1;

Not really. Arrays are limited to an int in size. You would be using more memory for the calculation and have to cast the value down to a 32 bit value to use as an array index.

Or you could just write the code so it isn't vulnerable to integer overflow.

Not in assemly, where it's trivial to shift right with carry.

It's not possible, because low and high are of type int, which is always lesser than uint_nax/2