Counting Inversions in Lists

In a recent paper, Ajtai et al. [1] give a randomized streaming algorithm to count the number of inversions in a stream L e [m] sup n using two passes and O(e sup -1 square root n log n (log m + log n)) space. Here, we present a simple randomized streaming algorithm for the same problem that uses one pass and O(e sup -3 log sup 2 n log m) space. Our algorithm is based on estimating quantiles of the items already seen in the stream, and using that to estimate the number of inversions involving each element.