8.6 Performance Characteristics of Mergesort

Table 8.1 shows the relative effectiveness of the various improvements that we have examined. As is often the case, these studies indicate that we can cut the running time by half or more when we focus on improving the inner loop of the algorithm.

In addition to netting the improvements discussed in Section 8.2, a good Java VM implementation might avoid unnecessary array accesses to reduce the inner loop of mergesort to a comparison (with conditional branch), two index increments ( k and either i or j ), and a test with conditional branch for loop completion. The total number of instructions in such an inner loop is slightly higher than that for quicksort, but the instructions are executed only N lg N times, where quicksort's are executed 39 percent more often (or 29 percent with the median-of-three modification). Careful implementation and detailed analysis are required for more precise comparison of the algorithms in particular environments; nonetheless, we do know that mergesort has an inner loop that is slightly longer than that of quicksort.

Table 8.1. Empirical study of mergesort algorithms

These relative timings for various sorts on random files of integers indicate that standard quicksort is about twice as fast as standard mergesort; that adding a cutoff for small files lowers the running times of both bottom-up and top-down mergesort by about 15 percent; that top-down mergesort is about 10 percent faster than bottom-up mergesort for these file sizes; and that even eliminating the cost of the file copy (the method used in the Java system sort ) leaves mergesort substantially slower than quicksort for randomly ordered files.
		top-down			bottom-up
N	Q	T	T*	O	B	B*	S
12500	23	27	16	19	30	20	19
25000	20	43	34	27	42	36	28
50000	45	91	79	52	92	77	56
100000	95	199	164	111	204	175	117
200000	201	421	352	244	455	396	256
400000	449	904	764	520	992	873	529
800000	927	1910	1629	1104	2106	1871	1119
Key : Q Quicksort, standard (Program 7.1) T Top-down mergesort, standard (Program 8.1) T* Top-down mergesort with cutoff for small files O Top-down mergesort with cutoff and no array copy B Bottom-up mergesort, standard (Program 8.5) B* Bottom-up mergesort with cutoff for small files S `java.util.Arrays.sort`

As usual, we must add the caveat that pursuit of improvements of this nature, although irresistible to many programmers, can sometimes lead to marginal gains and should be taken on only after more important considerations have been resolved. In this case, mergesort has the clear advantages over quicksort that it is stable and is guaranteed to run fast (no matter what the input), and the clear disadvantage that it uses extra space proportional to the size of the array. If these factors point to the use of mergesort (and speed is important), then the improvements that we have suggested may be worth considering, along with careful study of VM performance, the use of native C code, special properties of the machine architecture, and so forth.

On the other hand, we must also add the usual caveat that programmers should always have one eye on performance in order to avoid costs that are completely unnecessary. All programmers (and authors!) have suffered the embarrassment of having a simple unnoticed characteristic of an implementation dominate all that implementation's other sophisticated mechanisms. It is not unusual for a factor-of-2 improvement in running time to be found when implementations are examined carefully in this way. Frequent testing is the most effective defense against last-minute surprises of this type.

We discussed these points at length in Chapter 5, but the allure of premature optimization is so strong that it is worthwhile to reinforce them each time that we study techniques for performance improvement at this level of detail. For mergesort, we are comfortable with optimizing because Properties 8.1 through 8.4 essentially characterize the performance and hold for all the implementations that we have examined: Their running time is proportional to N log N and is insensitive to the input (see Figure 8.8); they use extra space; and they can be implemented in a stable manner. Maintaining these while improving the running time is generally not difficult.

Figure 8.8. Sorting of various types of files with bottom-up mergesort

The running time for mergesort is insensitive to the input. These diagrams illustrate that the number of passes taken by bottom-up mergesort for files that are random, Gaussian, nearly ordered, nearly reverse ordered, and randomly ordered with 10 distinct key values (left to right) depends only on the file size, no matter what the input values are. This behavior is in sharp contrast to that of quicksort and to that of many other algorithms.

graphics/08fig08.gif

Exercises

8.31 Implement bottom-up mergesort with no array copy.

8.32 Develop a three-level hybrid sort that uses quicksort, mergesort, and insertion sort to get a method that is as fast as the most efficient quicksort (even on small files) but can guarantee better than quadratic performance in the worst case.

Top