Quadripartite Sort

✍ Scribed by Jing-Chao Chen

• Book ID: 102579399
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 159 KB
• Volume: 28
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1998.0935

✦ Synopsis

This paper presents an efficient and practical sorting algorithm, called Quadripartite Sort. It lies between MergeSort and QuickSort. This algorithm sorts n elements using bounded workspace and n log n q 1.75n comparisons in the worst case. By empirical testing, we conjecture that this algorithm needs approximately n log n y n comparisons on average. When using m-way merging strategy, where m is a larger constant, this algorithm becomes an in-place sorting algorithm whose comparison plus exchange total is absolutely minimum among known constant workspace algorithms. For example, using a 256-way merging, the comparison plus Ž . exchange total required is approximately 1.2495n log n q O n in the worst case.