Binary Merging/Sorting Algorithm

This paper describes the application of the binary merging tree to the design of the sorting algorithm, to merge m sorted blocks instead of sorting n elements. This algorithm's time complexity is O (nlogm). m∈(1,n/2) for the worst case. Its performance is O(n) for the optimal case, and the comparison time is not more than nlogm +n—1, m∈(1,n/2). This is obviously superior to the currently popular sorting algorithms whose time cost is O (nlogn).