Fringe analysis for Extquick: Anin situ distributive external sorting algorithm

Autor:	Walter Cunto, Gaston H. Gonnet, Patricio V. Poblete, J. Ian Munro
Rok vydání:	1991
Předmět:	Sorting algorithm External sorting Hybrid algorithm Search tree Computer Science Applications Theoretical Computer Science Tree (data structure) Computational Theory and Mathematics Distributive property Data_FILES Algorithm Time complexity Quicksort Information Systems Mathematics
Zdroj:	Information and Computation. 92:141-160
ISSN:	0890-5401
DOI:	10.1016/0890-5401(91)90007-o
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::656dee019db7bd9747f19c607b2df204 https://doi.org/10.1016/0890-5401(91)90007-o Zobrazit plný text záznamu