Counting Inversions in Lists
journal contributionposted on 01.03.2005, 00:00 by Anupam Gupta, Francis X. Zane
In a recent paper, Ajtai et al.  give a streaming algorithm to count the number of inversions in a stream Lε[m]n using two passes and O(ε−1-√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(ε−3 log2 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.