We consider the problem of sorting streaming data where each unit of data is large and thus only a small number of units can be stored in memory. The goal is to produce a permutation matching the ordering of the input data as closely as possible. The performance is measured via permutation distortion metrics and mutual information. In addition to the big data setting, this problem is applicable to learning user rankings of movies, books, etc, where users can remember reliable information about only a small number of past items. We present algorithms whose performance is within a constant factor of the best possible. In addition to the traditional distortion metrics, we present results for weighted distances that are more sensitive to errors occurring in the top portions of permutations.