the sorting problem and algorithms for solving it huang and langston [ describe how to merge two sorted lists in-place in linear time our set adt is derived from the set adt of ahohopcroftand ullman [ the standard quick-sort algorithm is due to hoare [ more information about randomizationincluding chernoff boundscan be found in the appendix and the book by motwani and raghavan [ the quick-sort analysis given in this is combination of an analysis given in previous edition of this book and the analysis of kleinberg and tardos [ the quick-sort analysis of exercise - is due to littman gonnet and baeza-yates [ provide experimental comparisons and theoretical analyses of number of different sorting algorithms the term "prune-and-searchcomes originally from the computational geometry literature (such as in the work of clarkson [ and megiddo [ ]the term "decrease-and-conqueris from levitin [ text processing