Counting inversions in lists

摘要

In a recent paper, Ajtai et al. [1] give a streaming algorithm to count the number of inversions in a stream Lε[m]ⁿ using two passes and O(ε⁻¹-√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(ε⁻³ log² 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.