<p>Sounds like you might want to read <a href="http://arxiv.org/abs/0907.0884" rel="noreferrer">Self-Improving Algorithms</a>: they achieve an eventual optimal expected running time for <em>arbitrary</em> input distributions.</p>

<blockquote>
  <p>We give such self-improving algorithms
  for two problems: (i) sorting a
  sequence of numbers and (ii) computing
  the Delaunay triangulation of a planar
  point set. Both algorithms achieve
  optimal expected limiting complexity.
  The algorithms begin with a training
  phase during which they collect
  information about the input
  distribution, followed by a stationary
  regime in which the algorithms settle
  to their optimized incarnations.</p>
</blockquote>

<p>If you already know your input distribution is approximately Gaussian, then perhaps another approach would be more efficient in terms of space complexity, but in terms of expected running time this is a rather wonderful result.</p>
Sorting algorithms for data of known statistical distribution?
<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>