  We prove a general lower bound on the average-case complexity of Shellsort:
the average number of data-movements (and comparisons) made by a $p$-pass
Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p})$ for every
$p$. The proof method is an incompressibility argument based on Kolmogorov
complexity. Using similar techniques, the average-case complexity of several
other sorting algorithms is analyzed.
