Comb Sort, también denominado de Peine o Cardado, es un algoritmo de ordenación que mejora el algoritmo de Burbuja. Utiliza la misma acción que Shellsort para aumentar la brecha en las comparaciones e intercambios, el valor empírico del factor de reducción para extender la brecha es (1 – eφ ) ≈ 1,24733095, también √2 = 1,259. La mayoría de sus implementaciones usa 1,3, que es el espacio de trabajo (distancia entre elementos) que comienza con un tamaño grande y se va reduciendo en cada iteración, en ese factor, hasta alcanzar el valor 1. Estos valores han estado durante mucho tiempo en controversia, pero la realidad es la que es y en estos momentos el algoritmo está por detrás de otros en rendimiento.
| Rendimiento – Complejidad | |||
| Mejor caso Ω | Peor caso O | Media Θ | Espacio |
| (n log n) | (n²) | (n²) | O(1) |
Muchas publicaciones indican que fue Wlodzimierz Dobosiewicz quién lo desarrolló en 1.980, pero Donald E. Knuth y Robert W. Floyd quienes lo propusieron en “The Art of Computer Programming, Vol 3” de 1.973 como una variante de Shellsort. Otra fecha de autoría es la de 1.994 de Stephen Lacey y Richard Box.
En el algoritmo de ejemplo se propone la variante de Stephen Lacey – Richard Box: brecha = (brecha * 10) / 13 que da un factor superior a 1,3.
Rendimiento.
Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.
