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

41 result[i] = left[i1]; // take from left
42 i1++;
43 } else {
44 result[i] = right[i2]; // take from right
45 i2++;
46 }
47 }
48 }
49 }

The program produces the following output:

before: [14, 32, 67, 76, 23, 41, 58, 85]
after: [14, 23, 32, 41, 58, 67, 76, 85]

Figure 13.7 demonstrates the performance of our merge sort algorithm on a mod-
ern computer. The merge sort algorithm's performance is much better than that of the
selection sort algorithm. For example, whereas our selection sort test run needed over
41 seconds to sort 128,000 elements, the merge sort algorithm handled the same job
in a blistering 47 milliseconds. But what is merge sort's complexity class? It looks
almost like an O ( N ) algorithm, because the runtime only slightly more than doubles
when we double the array size.

1000
2000
4000
8000
16000
32000
64000
128000
256000
512000
1e6
2e6
4e6
8e6
1.6e7
3.3e7
6.5e7
1.3e8

N Runtime (ms)

0
0
0
0
0
15
16
47
125
250
532
1078
2265
4781
9828
20422
42406
88344

100000
90000
80000
70000
60000
50000
40000
30000
20000
10000
0

Input size (N)

Figure 13.7 Runtimes for merge sort algorithm