Visible surface plotting program
Thomas J. Wright · Communications of the ACM · 1974
Hillmore's modification), it would take 13 q-7 -I-7 q-1 q-1 q-1 q-1 = 31 comparisons to sort an array of length eleven.If, in addition, the splitting routine uses only k = n comparisons per scan, then only 11 q-5 q-5 q-1 q-1 q-1 + 1 = 25 comparisons would be needed to sort that same array.The foregoing illustrates a recursive procedure that generates a certain sequence of array sizes n~ and the corresponding minimum number of comparisons c~.The cl depend on the number of comparisons per scan and on the handling of subarrays of length two; the ni depend on the number of elements in the middle subarrays.(The values of c~ obtained in this way are probably local minima of the variation of c with ii, since the nl are deliberately chosen to make equal-length subatrays possible--no other values of n permit this.)Table A-I shows values of cl for middle subarrays of length one.There are two sets of values for each value of k: (1) for the case that subarrays of length two are partitioned, and (2) for the case that subarrays of length two are sorted.Values of log2 (n~!) are also shown.(These were obtained by summation, according to log2 n! = logs n -t-log ~ [(n -1)!].)All numbers in Table A-1 have been divided by n logs (n), as described in Section 3. Note first that for the array sizes shown, values of the approximation n logs (17) are considerably larger than log2 (n!).Nevertheless, it happens that n logs (n) predicts the minimum number of comparisons quite well for a routine like quicksort (k = n -t-2, case 1).However, its values, and those of log2 (n!) as well, are too large for a routine like quickersort (k = n, case 2)~ and even more so for a routine with k = n --1.Algorithms L.D. Fosdick and A.K. Cline, Editors Submittal of an algorithm for consideration for publication in Communications of the ACM implies unrestricted use of the algorithm within a computer is permissible.