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 n containing σ distinct elements using one pass and o(n log σ) bits of memory, it is generally necessary and sufficient that its entropy H = o(log σ). Specifically, if s = {s1,..., sn} and si1,..., sin is the stable sort of s, then we can compute i1,..., in in one pass using O((H +1)n) time, O(σ) words plus O((H +1)n) bits of memory, and a simple combination of classic techniques. On the other hand, in the worst case it takes Ω(Hn) bits of memory to compute any sorted ordering of s in one pass. Keywords: Sorting; Streaming algorithms; Compression. 1