Fringe analysis for Extquick: Anin situ distributive external sorting algorithm

A newin situ external sorting algorithm, to be calledExtquick, is developed and its time and space performance are analysed. It is shown that Extquick performs more efficiently than similarin situ sorting algorithms based on Quicksort that appear in the literature. Since the computational tree of Quicksort-like sorting algorithms is equivalent to a search tree, techniques that model the time complexity of such a structure are then used for the analysis of Extquick.

Authors

• Walter Cunto
• Gasto´n H. Gonnet
• J. Ian Munro
• Patricio V. Poblete

Keywords

No keywords are indexed for this paper.