Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 812

However, merge sort is actually an O ( N log N ) algorithm. A formal proof of this
statement is beyond the scope of this topic, but a common-sense chain of reasoning is
as follows: We have to split the array in half repeatedly until we hit the algorithm's
base case, in which the subarrays each contain 1 element. For an array of size N ,we
must split the array log 2 N times. At each of those log N steps, we have to do a linear
operation of order N (merging the halves after they're sorted). Multiplying these
operations' runtimes together produces a O ( N log N ) overall runtime.
The preceding algorithm runtime analysis is informal and not rigorous. As with
other recursive algorithms, a precise analysis of merge sort's performance is compli-
cated and requires mathematical techniques such as recurrence relations, which are
not discussed in this topic.
Did You Know?
Cost of Java Array Allocation
Earlier in the chapter we mentioned that variable declaration and assignment can
be thought of as taking some constant amount of time. That is usually true, but
there is one important exception: initializing arrays. Suppose you were to execute
this line of code:
int[] list = new int[n];
Executing this line of code requires the computer to allocate a block of mem-
ory for the array. That can generally be done in a constant amount of time. But
Java also insists on auto-initializing all array elements to 0 and that takes time
proportional to n .
This subtlety of Java has stung several textbook authors who were translating
textbooks from C and C++ into Java. When they were writing a solution to the
merge sort algorithm, they included code that would allocate a temporary array
as large as the entire array every time they did a merging operation.
For an array of size n , there are n different merging operations. If each one
requires the computer to auto-initialize an array of length n , then the overall sort-
ing algorithm becomes an O( N 2 ) algorithm. That is considerably slower than the
O( N log N ) behavior that we expect for a merge sort algorithm.
The authors made this mistake because C and C++ don't auto-initialize arrays.
That means that their code ran fast in those languages, and when they tested their
code they found that it behaved as expected. They apparently translated their
code into Java without retesting whether it was fast. More than one textbook
author has made this mistake, but out of respect for our fellow authors (and
recognizing that we make mistakes ourselves), we won't name any names!