AbstractOur 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 beadaptive. We introduce randomization to achieve this goal; the first time randomization has used to obtain adaptive sorting algorithms. We investigate three randomized algorithms.1Randomized Merge Sort, which is expected Runs‐optimal;2Randomized Quicksort, which is Exchange‐sensitive, that is, it takes Θ(|X|[1+log(Exc(X)+1)]) time in the expected case; and3Skip Sort, whichh isInversions‐, Runs‐, andExchhange‐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 ofQuicksortwere baed only on simulation results,; our claims are based on a formal analysis. © 1993 John Wile