  We investigate the complexity of sorting in the model of sequential quantum
circuits. While it is known that in general a quantum algorithm based on
comparisons alone cannot outperform classical sorting algorithms by more than a
constant factor in time complexity, this is wrong in a space bounded setting.
We observe that for all storage bounds n/\log n\ge S\ge \log^3 n, one can
devise a quantum algorithm that sorts n numbers (using comparisons only) in
time T=O(n^{3/2}\log^{3/2} n/\sqrt S). We then show the following lower bound
on the time-space tradeoff for sorting $n$ numbers from a polynomial size range
in a general sorting algorithm (not necessarily based on comparisons):
TS=\Omega(n^{3/2}). Hence for small values of S the upper bound is almost
tight. Classically the time-space tradeoff for sorting is TS=\Theta(n^2).
