Known worst-case performance of fast sorts

M(n) - worst-case number of comps by Mergesort (same # of comps as Binary insertion sort)
F(n) - worst-case number of comps by Merge insertion sort (not covered in class)
S(n) - worst-case number of comps by the optimal sort for n
LB(n)- information-theoretic lower bound on the worst-case number of comps by any sorting = Ceil[lg n!]

n	1 2 3 4 5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  27  28  29  30  31  32  33 
M(n)	0 1 3 5 8 11 14 17 21 25 29 33 37 41 45 49 54 59 64 69 74 79 84 89 94 99 104 109 114 119 124 129 135  
F(n)	0 1 3 5 7 10 13 16 19 22 26 30 34 38 42 46 50 54 58 62 66 71 76 81 86 91  96 101 106 111 116 121 126
S(n)	0 1 3 5 7 10 13 16 19 22 26 30 34 38 42 45?         62 66 71                               
LB(n)	0 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 53 57 62 66 70 75 80 84 89  95  98 103 108 113 118 123

Empty spaces mean "unknown" (could be F(n), LB(n), or in between).

? means that the value seems plausible (likely) but has not been proved.

M(13) = 37 was computed in class by running a worst case of Mergesort and was undefeated by another scheme of optimal linear merging. 
If merge insertion were used, the number of comps would have been 34 (optimal).

The same was done for M(21) = 74 and posted in file CSC401/Website/Merge21.pdf
If merge insertion were used, the number of comps would have been 66 (optimal).

The smallest n definitely known to be non-optimal for F is 47:
F(47) = 201 while S(47) was effectively shown = 200 or less.
F is non-optimal for infinitely many n's, starting with n = 189.


Known average-case performance of fast sorts

Qavg(n) - average-case number of comps by QuickSort
Favg(n) - average-case number of comps by Merge insertion sort (not covered in class)
Savg(n) - average-case number of comps by the optimal sort for n
LBavg(n)- information-theoretic lower bound on the average-case number of comps by any sorting = min-epl(n!)/n!


n	    1 2 3       4       5        6        7       8        9        10
Qavg(n) 0 1 2.66667 4.83333 7.4      10.3     13.4857 16.9214  20.5794  24.4373
Favg(n)	0 1 2.66667 4.66667 6.93333  9.6      12.4571 15.4571 >18.5552 >21.8442
S(n)    0 1 2.66667 4.66667 6.93333 <9.6     >12.3746          18.5552  21.8442
LBavg(n)0 1 2.66667 4.66667 6.93333  9.57778  12.3746 15.3746  18.5552  21.8442


To avoid fractions, we will use these total (cumulative) numbers, instead:

n!*Qavg(n) - total number of comps by QuickSort
n!*Favg(n) - total number of comps by Merge insertion sort (not covered in class)
n!*Savg(n) - total number of comps by the optimal sort for n
n!*LBavg(n)- information-theoretic lower bound on the total number of comps by any sorting = min-epl(n!)

n	        1 2 3  4   5    6     7     8       9        10
n!*Qavg(n)  	0 2 16 116 888  7416  67968 682272  7467840  88678080
n!*Favg(n)	0 2 16 112 832  6912  62784 623232 >6733312 >79268096
n!*S(n)     	0 2 16 112 832 <6912 >62368         6733312  79268096
n!*LBavg(n)	0 2 16 112 832  6896  62368 619904  6733312  79268096


There is a method of sorting 6 elements that performs less comparisons on average than Favg(6). 
So, 
6!*S(6) < 6!*Favg(6) = 6912. 
Therefore Merge insertion sort is not average-case optimal for n = 6, 
although it is worst-case optimal for n = 6. 
So, 
worst-case optimality for given n does not imply average-case optimality for that n.

It is not known if average-case optimality for n necessarily implies worst-case optimality for n.

However, for any n, if a sorting algorithm A(n) matches the avarage-case lower bound then A(n) is not only average-case optimal but also worst-case optimal (as any decision tree with minimal epl has also the least depth).  

There is no way of sorting 7 elements that would perform only 62368 comparisons in total (for all 7! permutations). 
So,
7!*S(7) > 7!*LBavg(7) = 62368.

There is a way of sorting 9 elements and 10 elements that matches the lower bound.

Not much more is known as of today (03.25.2014).