ABSTRACT
Sorting algorithms permeate nearly every area of computing. Accordingly, we as-
sume the reader is familiar with the basic sorting concepts and algorithms, and the
operation of the latter with uniformly distributed data. In the context of sorting, uni-
form distribution means that an input of size n for sorting consists of n distinct values,
typically in an array, and each of the n! possible permutations is equally likely. Since
our aim is to revisit some of these algorithms and evaluate their performance under
different probability data models, we found it useful to discuss briefly their princi-
ples, and make the treatment here self-contained. We plan to characterize the opera-
tion of some sorting algorithms on uniform random data but not revisit the analysis.
This chapter addresses the way some of those algorithms behave under alternative
data models. The question of interest is: To what extent do they maintain the proper-
ties they are known for (known for uniform data) when the situation changes? One
can ask this question about any known algorithm, and the answers are often tinged
with surprise.
