Premium
Randomized adaptive sorting
Author(s) -
EstivillCastro Vladimir,
Wood Derick
Publication year - 1993
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240040103
Subject(s) - quicksort , sorting algorithm , merge algorithm , sorting , merge sort , computer science , sort , algorithm , merge (version control) , randomized algorithm , mathematics , parallel computing , information retrieval
Our goal is to design practical sorting algorithms that require time proportional not only to the size of the input but also to the disorder in the input. Such sorting algorithms are said to be adaptive . We introduce randomization to achieve this goal; the first time randomization has used to obtain adaptive sorting algorithms. We investigate three randomized algorithms.1 Randomized Merge Sort , which is expected Runs‐optimal; 2 Randomized Quicksort , which is Exchange‐sensitive, that is, it takes Θ(|X|[1+log(Exc(X)+1)]) time in the expected case; and 3 Skip Sort , whichh is Inversions ‐, Runs‐, and Exchhange ‐optimal.The three sorting algorithms are simple and practical, in contrast to previous adaptive sorting algorithms that used complex data structures. Moreover, previous claims about the performance of adaptive variants of Quicksort were baed only on simulation results,; our claims are based on a formal analysis. © 1993 John Wiley & Sons. Inc.