Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)

Paul M. B. Vitanyi

Recently, many results on the computational complexity of sorting algorithms were obtained using Kolmogorov complexity (the incompressibility method). Especially, the usually hard…