コムソート（）やコームソートや櫛（くし）ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した。バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。挿入ソートをシェルソートに改良したときと同様の改良を施す。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。public static void combSort(int[] data) {private static void swap(int[] a, int i, int j) {void comb_sort(int* array, int size) {動作例としてという数列を昇順に整列してみる。このとき n=8 だから h=8÷1.3≒6 から始める。8と2、4と1を比較して2回交換を行う。次は h = 6÷1.3 ≒ 4。2と6、1と5のように比較してゆき、7と4のみが交換される。以下 h は 3 → 2 → 1 の順に減っていくのでh=3：交換なしh=2：交換なしh=1：交換3回この例では6回の交換で整列が終了した。h=9,10となったとき、強制的にh=11とすることで高速化したアルゴリズムを、Comb sort 11と呼ぶ。hが9→6→4→3→2→1や10→7→5→3→2→1と遷移するよりも、11→8→6→4→3→2→1と遷移する方がうまく櫛が梳けるためである。

出典:wikipedia