Compares of Bottom-up Mergesort

It is fun to spot a mistake in a technical book. (Knuth has made it cool by sending out cheques to the error spotters.) Recently, I found a mistake while looking through the chapter on mergesort in Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne.

There is a proposition in the chapter which states that:

bottom-up mergesort uses between 0.5 N lg N and N lg N compares and 6 N lg N array accesses to sort an array of N items.

There is a small error in the proof. It states that:

the number of passes through the array is precisely floor( lg N ) which is precisely the value of n such that 2^n <= N < 2^n+1

This is wrong when N is not a power of 2. For example, if N is 7, then the array cannot be sorted in 2 passes, it needs at least 3, which is ceil( lg N ).

So, the correct statement in the proof should be:

the number of passes through the array is precisely ceil( lg N ) which is precisely the value of n such that 2^n-1 < N <= 2^n

I contacted the authors about this and was surprised when co-author Kevin Wayne promptly replied back confirming the error. He even added the correction to the errata webpage of their book 😊