A comparison of sorts, revisited. Howard Kaplon.

A Comparison of Sorts, Revisited

During a recent search for a better sorting routine, a colleague offered the article "A Comparison of Sorts' by John Grillo (Nov/Dec 1976--Some people never discard their issues of Creative--EBS). Previously, I had always used the bubble sort technique for exactly the reasons given in the Grillo article: it was a simple technique and one which was very familiar. According to the article, the Shell-Metzner sorting routine would end the search.

However, another colleague suggested that a technique called quicksort described in The Art of Computer Programming, Vol. III by Knuth be investigated. Having programmed this algorithm and modified it slightly, I wanted to see how it compared with the Shell-Metzner sort.

An empirical approach seemed the most direct way to compare the two sorting routines. The bubble sort was also included in the comparisons. At the end of this article (Listing 1) is the Basic program I used to make the comparisons. It is the Basic program given in "A Comparison of Sorts' that was modified for use on a Univac 1106 system and had the quicksort technique appended to it.

Tables I and I-A summarize information on sorting arrays of 10, 20, 50, 100, 200, 500, and 1000 items by each of the three techniques. Additionally, arrays of 2000, 3000, and 4000 items were sorted by the Shell-Metzner and quicksort techniques. Each of the arrays consisted of a random sample generated from a normal distribution with a mean of 5000 and a standard deviation of 2000. The codes are: T = time of execution in milliseconds on a Univac 1106 time sharing system provided by the Maryland State Colleges Information Center, S = number of times that pairs of elements were switched, C = number of times that pairs of elements were compared, and N = number of items in the array.

As in the Grillo article, a regression model of the form T = AN(B) was used to predict the sorting time (T) from the array size (N). Table II gives the estimated regression equation for each of the three techniques. Using these equations and extrapolating, I calculated the predicted sorting times for large arrays as shown in Table III.

Differences between the values presented in Tables I, I-A and III of this article and the corresponding values that Grillo presented may be attributed to the different operating systems. However, the figures themselves are not nearly as important as the comparison among the three techniques.

What has been accomplished? First of all, we see the logic of the quicksort algorithm is much clearer than that of the Shell-Metzner algorithm. Briefly, the quicksort routine chooses a pivot element (the first element in this case) of the array and divides the array into two subarrays such that the left subarray contains all of the elements that are less than the pivot. The larger of the subarrays is put on a stack. The smaller subarray is further divided by its pivot into two subarrays. This process is repeated with each larger subarray being put on the stack until a smaller subarray has fewer than ten elements. This subarray is then bubble sorted, and the last subarray on the stack is examined. It is either divided or bubble sorted depending on whether it has at least ten or fewer than ten elements. Since all of the elements in each subarray are less than all of the elements in the next subarray to the right, after each subarray has been sorted, the sorted subarrays form the complete sorted array.

Secondly, one may compare the sorting times of the three techniques. Using the equations in Table II, I estimated that quicksort is 0.214N(0.772) times as fast as the bubble sort and 1.125N0.053 times as fast as the Shell-Metzer sort. From these estimates one may conclude that quicksort has the fastest sorting execution time and as the size of the array increases, the advantages of quicksort over the other two sorts also increase.

Finally, Harold Lorin indicates that quicksort with some minor modifications, as done by Richard C. Singleton, on the choice of the pivot and the sorting technique for the subarrays with less than ten elements may be the fastest of the currently known sorting techniques.

Since there is some theory to indicate that the sorting times of the bubble sort, Shell-Metzner sort, and quicksort are proportional to N2, Nln(N), and Nln(N) respectively, alternate regression models of T = KN2, T = KNln(N), and T = KNln(N) respectively were set up. For all three techniques, the estimated regression equations were computed using the seven data points. Then, with the additional data when N = 2000, 3000, and 4000 added one point at a time, three additional estimated regression equations were computed for each of the Shell-Metzner and quicksort techniques. These equations are given in Table IV. For the Shell-Metzner and quicksort techniques, the four estimated values of K were averaged. These average estimated regression equations, the standard deviations of K, and the equation for the bubble sorting time are given in Table V. The extrapolated sorting times for large arrays are shown in Table VI.

The conclusions that may be drawn from Table V are very similar to those already drawn from Table II, except that quick-sort is now predicted to be a constant 1.663 times as fast as Shell-Metzner. However, I think that the values of extrapolated predicted sorting times in Table VI are more accurate than those in Table III when executed on the Univac 1106.

In conclusion, while the understanding of the logic of the Shell-Metzner sort algorithm provides an interesting exercise, and while its sorting time is faster than that of the bubble sort, the delayed replacement sort and several other techniques, it is less efficient than quicksort. And so it seems that when internal sorting techniques are discussed, quicksort should be among those presented. Among the advantages of quicksort are: it allows for experimentation with different simple sorting routines for the subarrays of fewer than ten elements; it allows for variation in the number of elements at which the smaller subarray is to be bubble or otherwise simple sorted to optimize the execution time on each operating system; and it is easily programmed, clear, and quick.

Table: Table I. Sort Execution Data.

Table: Sort Execution Data.

Table: Estimated Regression Equations.

Table: Extrapolated Predicted Sorting Times.

Table: Alternative Estimated Regression Equations.

Table: Average Alternative Estimated Regression Equations.

Table: Alternative Extrapolated Predicted Sorting Times.

Table: Listing 1.

Photo: Quicksort Flowchart