EXPLOITING FEW INVERSIONS WHEN SORTING - SEQUENTIAL AND PARALLEL ALGORITHMS

We consider the problem of taking advantage of existing order within t he input sequence when sorting. The measure of presortedness used is t he number of inversions. Let X be a sequence of length n and let Inv(X ) be the (unknown) number of inversions in X. Our main results are: X can be sorted in-place, i.e. using only O(log n) bits of extra space, in time O(n log (Inv(X)/n)), which is optimal with respect to the numb er of inversions. Given p processors on an EREW PRAM, X can be sorted in time O(n log (Inv(X)/n)/p + log n), which is optimal with respect t o the number of inversions.