C. Bron
Abstract
Sorting by means of a two-way merge has a reputation of requiring a clerically complicated and cumbersome program. This ALGOL 60 procedure demonstrates that, using recursion, an elegant and efficient algorithm can be designed, the correctness of which is easily proved [2]. Sorting n objects gives rise to a maximum recursion depth of [log2(n - 1) + 2]. This procedure is particularly suitable for sorting when it is not desirable to move the n objects physically in store and the sorting criterion is not simple. In that case it is reasonable to take the number of compare operations as a measure for the speed of the algorithm. When n is an integral power of 2, this number will be comprised between (n × log2n)/2 when the objects are sorted to begin with and (n × log2n - n + 1) as an upper limit. When n is not an integral power of 2, the above formulas are approximate.
Supplemental Material
Available for Download
sort
- 1 Scowen, R.S. Quickersort, Comm. ACM8 (Oct. 1965), 669-670. Google Scholar
Digital Library
- 2 Bron, C., Proof of a merge sort algorithm, May 1971 (unpublished).Google Scholar
Recommendations
Non-Partitioning Merge-Sort: Performance Enhancement by Elimination of Division in Divide-and-Conquer Algorithm
ICTCS '16: Proceedings of the Second International Conference on Information and Communication Technology for Competitive StrategiesThe importance of a high performance sorting algorithm with low time complexity cannot be over stated. Several benchmark algorithms viz. Bubble Sort, Insertion Sort, Quick Sort, and Merge Sort, etc. have tried to achieve these goals, but with limited ...
Proportion Extend Sort
PROPORTION EXTEND SORT is a new sorting algorithm, the basic principle of which is similar to PROPORTION SPLIT SORT. This algorithm sorts a sequence by constructing three subproblems, using a QuickSort-like pivot technique and solving recursively each ...
A new sort algorithm: self-indexed sort
This paper presents a new sort algorithm, self-indexed sort (SIS), on an approach of non compare-based sorting. Results on time complexity O(n) and space complexity O(n+m) are achieved, where n is the size of data being sorted and m is the size of the ...
Comments