Java Reference
In-Depth Information
length of
a
. Moreover, at the beginning, we had to copy from a to
first
and
second
, yielding another 2n visits, for a total of 5n.
642
643
n
Merge Sort (milliseconds) Selection Sort (milliseconds)
10,000
40
786
20,000
73
2,148
30,000
134
4,796
40,000
170
9,192
50,000
192
13,321
60,000
205
19,299
If we let T(n) denote the number of visits required to sort a range of n elements
through the merge sort process, then we obtain
(
n
2
) (
n
2
)
T(n) =T +T +5n
because sorting each half takes T(n/2) visits. Actually, if n is not even, then we have
one subarray of size (nɨl)/2 and one of size (n+1)/2. Although it turns out that this
detail does not affect the outcome of the computation, we will nevertheless assume
for now that n is a power of 2, say n=2
m
. That way, all subarrays can be evenly
divided into two parts.
Figure 2
Merge Sort Timing (blue) versus Selection Sort (red)
643
