On: Nearly all binary searches and mergesorts are broken (2006)

[flupe]

The problem is not solved by using unsigned ints though, because it stems from integer overflow. I'm afraid your implementations are, alas, also incorrect.

[dataflow → flupe]

Confused, how does using unsigned integers not solve this particular problem? Doesn't the article itself show solutions with unsigned integers?

[a1369209993 → dataflow]

Example using 16-bit size_t for convenience:

  char array[60000]; // 5KB left for code and stack if not segmented
  size_t i = 40000;
  size_t j = 50000;
  size_t mid = (i+j)/2; // should be 45000
  // i+j = (size_t)90000 = 24464
  // mid = 24464/2 = 12232 != 45000

Larger integers make the necessary array size bigger, but don't change the overall issue.

[Filligree → dataflow]

Unsigned int is 32-bit, most address spaces are 48-bit or more.

[dataflow → Filligree]

Array.length is 32-bit in Java. This is from 2006.