„Discussion of a range of common sorting approaches... with emphasison, and analysis of, the distributions associated with thecomplexity measures on the algorithms.“ (American MathematicalMonthly, March 2002)
„... this book, in addition to being a reference book forcomputer professionals, is a good book to be used in teaching...“(Mathematical Reviews, 2003a)
A cutting-edge look at the emerging distributional theory ofsorting
Research on distributions associated with sorting algorithms hasgrown dramatically over the last few decades, spawning many exactand limiting distributions of complexity measures for many sortingalgorithms. Yet much of this information has been scattered indisparate and highly specialized sources throughout the literature. In Sorting: A Distribution Theory, leading authority Hosam Mahmoudcompiles, consolidates, and clarifies the large volume of availableresearch, providing a much-needed, comprehensive treatment of theentire emerging distributional theory of sorting.
Mahmoud carefully constructs a logical framework for the analysisof all standard sorting algorithms, focusing on the development ofthe probability distributions associated with the algorithms, aswell as other issues in probability theory such as measures ofconcentration and rates of convergence. With an emphasis onnarrative rather than technical explanations, this exceptionallywell-written book makes new results easily accessible to a broadspectrum of readers, including computer professionals, scientists, mathematicians, and engineers. Sorting: A DistributionTheory:
* Contains introductory material on complete and partialsorting
* Explains insertion sort, quick sort, and merge sort, among othermethods
* Offers verbal descriptions of the mechanics of the algorithms aswell as the necessary code
* Illustrates the distribution theory of sorting using a broadarray of both classical and modern techniques
* Features a variety of end-of-chapter exercises
Research on distributions associated with sorting algorithms hasgrown dramatically over the last few decades, spawning many exactand limiting distributions of complexity measures for many sortingalgorithms. Yet much of this information has been scattered indisparate and highly specialized sources throughout the literature. In Sorting: A Distribution Theory, leading authority Hosam Mahmoudcompiles, consolidates, and clarifies the large volume of availableresearch, providing a much-needed, comprehensive treatment of theentire emerging distributional theory of sorting.
Mahmoud carefully constructs a logical framework for the analysisof all standard sorting algorithms, focusing on the development ofthe probability distributions associated with the algorithms, aswell as other issues in probability theory such as measures ofconcentration and rates of convergence. With an emphasis onnarrative rather than technical explanations, this exceptionallywell-written book makes new results easily accessible to a broadspectrum of readers, including computer professionals, scientists, mathematicians, and engineers. Sorting: A DistributionTheory:
* Contains introductory material on complete and partialsorting
* Explains insertion sort, quick sort, and merge sort, among othermethods
* Offers verbal descriptions of the mechanics of the algorithms aswell as the necessary code
* Illustrates the distribution theory of sorting using a broadarray of both classical and modern techniques
* Features a variety of end-of-chapter exercises
