Presorting algorithms: An average-case point of view

We introduce the concept of presorting algorithms, quantifying and evaluati ng the performance of such algorithms with the average reduction in number of inversions. Stages of well-known algorithms such as Shellsort and quicks ort are evaluated in such a framework and shown to cause a meaning drop in the inversion statistic. The expected value, variance and generating functi on for the decrease in number of inversions are computed. The possibility o f "presorting" a sorting algorithm is also investigated under a similar fra mework. (C) 2000 Elsevier Science B.V. All rights reserved.