Re:Nearly All Binary Searches and Mergesorts Are Broken (2006)
by pclmulqdq on Sunday November 06, 2022 @10:34AM
(#33493665)
No. This article explicitly mentions the "int" type, which in C, C++, and Java is 32 bits long. 32-bit ints are not large enough for this purpose: they can only index 2 billion items directly (which will overflow a lot given that a standard server now has 256-512 GB of RAM), and this average calculation hits problems at around 1 billion items. Overflows on 64-bit ints (when used to store 63-bit unsigned numbers) are not going to happen for a very long time.
[ Parent
| on HN ]
Re:Nearly All Binary Searches and Mergesorts Are Broken (2006)
by dataflow on Sunday November 06, 2022 @10:37AM
(#33493690)
Wasn't Array.length 32-bit on Java when the article was written? In fact, isn't it 32-bit even now?
Moreover I don't see how you deny that using signed would lose functionality in this case—it's pretty undeniable that it gives the wrong answer in cases where unsigned would give the correct answer; the code is right in the article and you can test it out. This is true irrespective of any other cases that neither might handle correctly (assuming you believe any exist, but see my previous paragraph).
Re:Nearly All Binary Searches and Mergesorts Are Broken (2006)
by pclmulqdq on Sunday November 06, 2022 @10:58AM
(#33493939)
I didn't say that a signed int would be fine. I said that a signed 64-bit int would be fine.
Moreover, it is trivial to convert from a 32-bit signed or unsigned type to a 64-bit int, so you are not constrained by the size type of Java.