SHELL SORT

Debe su nombre al ingeniero y matemático estadounidense Donald Shell , que lo publicó en la revista Communications of the ACM en 1959.

Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.

CARACTERISTICAS
-Se trata de un algoritmo de ordenación interna; los datos están en memoria principal. Podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.

-Se basa en comparaciones e intercambios.

-Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.

-El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2). 

-En cierto modo, puede considerarse una ampliación del algoritmo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.

-No es un algoritmo en-línea.