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