Some New Results on Pair-wise Compare Sorting

In this section I present you with some hint on interested and new results on the Comparison base Sorting Problem. These results include proof along with test results from implementation algorithms, and they also disprove a few notion held by individuals within the academic community. .

In-place Sorting with Nlog2(N) - log2 Comparisons and 3N moves

Here we present an algorithm that used stored information gathered during a sort operation to reduce the number of comparisons to N\ceil{log2(N)} - \ceil{log2(N)} and the number of data moves to no more than 3N. Where N is the number of records in the data file been sorted. A part of the abstract for this algorithm is given in the following image file but an explanation of the whole algorithm is not given as a patent for the algorithm is been processed. The algorithm is implemented on a parallel system that does O(log2(N)) time sort.

The Theoretical Lower bound on the number of comparisons is base on a wrong assumption

Conclusion on the evaluation on the minimum number of comparisons that can be done by an algorithm in the average case is base on a assumption about pair wise comparisons and the information that is gathered and then used during the sorting process.

Here we give a proof that refutes this erroneous assumption along with an algorithm in support of the proof. .

Then I have some other interested ideas for reducing the number of data moves in an optimum sort algorithm to O(N). There is also a download file with a flowchart for LogicCoder that implements a algorithm for Kronrod's original in-place optimum merge algorithm. I will make these files available at a later date as a free download.


Values during the sorting operation are selected into sorted locations relative to each other base on pair wise comparisons and that information gained from pair wise comparisons can only be reused from a binary structure which is implicitly or explicitly within the structure of the algorithm.

It is interested to see that some well known sorting algorithm such as merge sort and quick-sort readily support these assumptions.

Although the assumption of the theory is correct for some pair wise comparison algorithms, the conclusion of the theorem cannot be correct. I.e. there are pair wise comparison sort algorithms which on average do less than $O(Nlog_2(N))$ comparisons to sort $N$ data values. Here in this presentation we construct a proof of this statement.

Consider the set of $N$ values in the set $D$ to be sorted. Assume that $D = {x_0, x_1, cdot x_{N-1}}$ is the original permutation of the set. Define the macro $Compare(x_i, x_j) = (true or false); i \ne j \in {0, 1, 2, \cdots N-1}$. We have that $Compare(x_i, x_j) --> Exchange(x_i, x_j) if Compare(x_i, x_j) = false given that i < j$. The theory assumes that for any known $Compare(x_i, x_j) = true$ this information is obtained only by comparison between $x_i$ and $x_j$ or from information implicitly or explicitly represented in in a binarystructure. This binary structure in some case is created by the algorithm explicitly in memory such as with heap sort or implicitly such as with binary insertion sort. Hence, such structure is often used to construct this proof.