コムソート - 通信用語の基礎知識

シェルソートと同じように数列を分割することにより、データの交換量が少なくなるようにした交換ソート。ソートの経過が、数列が櫛(コム)で梳かれているように見えることからコムソートと名づけられている。

最悪計算量はO(n²)であるが、数列の分割方法によってはO(n^1.25)程度の計算量になる。これはシェルソートと同じである

リンク