title: Sorting algorithms for data of known statistical distribution?
body: <p>It just occurred to me, if you know something about the distribution (in the statistical sense) of the data to sort, the performance of a sorting algorithm might benefit if you take that information into account.</p>
  <p>So my question is, are there any sorting algorithms that take into account that kind of information? How good are they?</p>
  <p>An example to clarify: if you know the distribution of your data to be Gaussian, you could estimate mean and average on the fly as you process the data. This would give you an estimate of the final position of each number, which you could use to place them close to their final position.</p>
  <p>I'm pretty surprised the answer isn't a wiki link to a thourough page discussing this issue. Isn't this a very common case (the Gaussian case, for example)?</p>
  <p>I'm adding a bounty to this question, because I'm looking for definite answers with sources, not speculation. Something like &quot;in the case of gaussian distributed data, XYZ algorithm is the fastest on average, as was proved by Smith et al. [1]&quot;. However any additional information is welcome.</p>