Big-oh statistics for average compares and moves of new patented sorting algorithm are 2- to 8-times less than for quick sort and radix sort

From "Dann Corbit" <dcorbit@solutionsiq.com>: > heap sort or merge sort are always n*log(n). For US Patent 5,926,815 "Binary sort access method and apparatus" [BSAM], the total number of moves [m] is on average [1]: m = ( ( ( ( b ^ 2) * ( int( ( n - 1) / b)) + ( ( mod (n - 1, b) + 1) ^ 2)) / 4) + ( b * ( int( ( n - 1) / b)))) . The number of compares [c] on average is m plus the number of compares with the initial binary search: c = ( int( 1 + log2( 1 + ( b * ( 0.5 * ( int( ( n - 1) / b)) * ( int( ( n - 1) / b) + 1)))))) + ( ( ( ( b ^ 2) * ( int( ( n - 1) / b)) + ( ( mod (n - 1, b) + 1) ^ 2)) / 4) + ( b * ( int( ( n - 1) / b)))) . The average performance of compares for heap sort, merge sort, and quick sort is n lg n + n. n n lg n BSAM BSAM Times fewer + n compares moves (compares) ------------- ------------ ---------- ---------- ----------- 100 764 381 372 2.01 1 000 10 966 3 754 3 738 2.92 10 000 142 877 37 520 37 497 3.81 100 000 1 760 964 375 017 374 988 4.70 1 000 000 20 931 569 3 750 033 3 749 997 5.58 10 000 000 2.4253497e+8 37 500 030 37 499 987 6.47 100 000 000 2.7575425e+9 3.75e+8 3.75e+8 7.35 1 000 000 000 3.0897353e+10 3.75e+9 3.75e+9 8.24 Hence for n from 100 to 1 000 000 000, BSAM performs from 2- to 8-times fewer compares and moves than do sorts with n lg n + n as averages. [1] Sedgewick, Robert and Flajolet, Phillipe. An Introduction to the Analysis of Algorithms. Addison-Wesley. 1996. p 337.