How to write a correct implementation of merge sort

Josh Bloch always has very interesting things to say. I came across this blog post by him accidentally, but it’s a very interesting point: most implementations of merge sort break down for really large arrays (unbelievably large arrays if you’re using a 64bit processor). The problem comes when the algorithm tries to calculate the index of the pivot: most implementations will do this:

mid = (low + high) / 2

but this will overflow if both low and high are very large. You can read the full article here.

I guess the take-home point here is to bear overflows in mind when performing integer arithmetic, especially in core areas of code where your data structures could potentially grow to an enormous size in the future (after all, “640K ought to be enough for anybody”).

Solution

Rather than calculating the average of the low and high bounds, calculate the difference between the two and use that to find the pivot:

mid = low + ((high - low) / 2)

(This is the most language neutral way of calculating it, although Josh does offer more efficient versions for languages with bit-shifting)

Advertisements

About this entry