Sorting streamed multisets

Sorting is a classic problem and one to which many others reduce easily. In the streaming model, however, we are allowed only one pass over the input and sublinear memory, so in general we cannot sort. In this paper we show that, to determine the sorted order of a multiset s of size If containing sigma >= 2 distinct elements using one pass and o(n log sigma) bits of memory, it is generally necessary and sufficient that its entropy H = o(log sigma). Specifically, if S = {S-1.....S-n) and S-i1.....S-in is the stable sort of s, then we can compute i(1).....i(n) in one pass using O((H + 1)n) time and O(Hn) bits of memory, with a simple combination of classic techniques. On the other hand, in the worst case it takes that much memory to compute any sorted ordering of s in one pass. (C) 2008 Elsevier B.V. All rights reserved.