Donald Shell propôs len/2
como o valor inicial do intervalo, e
ir dividindo por 2 a cada passo. O pseudo-código é o seguinte:
gap=len/2 while gap>0: apply InsertionSort, comparing i-gap and i, then i-2gap and i-gap, then i-3gap and i-2gap, etc.
Assim como no CombSort, a sequência de valores pega pelo intervalo é crucial para a performance do Shell sort. Em alguns casos patológicos raros, a sequência que usamos pode levar a uma performance O(n^2). Outras sequências foram propostas: os incrementos de Hibbard de 2k − 1 levam a uma complexidade de O(n^(3/2)) em casos ruins. incrementos de Pratt 2^i3^j levam a uma performance de O(nlog(n)log(n) nos piores casos. A existência de uma sequência levando a O(n log(n)) foi excluída por Poonen, Plaxton e Suel. Graças a esta performance, ShellSort é um candidato válido para arrays de várias centenas de milhares quando corretamente implementado.
No nosso caso, a array é pequena demais para se beneficiar destas otimizações. Se você ainda assim quiser, tome o intervalo inicial como o maior valor da série alvo ainda menor que o tamanho do array, e então use valores decrescentes da série.
Um fato interessante: Determinar a melhor sequência de intervalos para o shell sort se tornou um tema de pesquisa de nosso século em ciência da computação. Por exemplo, um artigo de 2001 introduz a seguinte sequência, que parece ser a melhor na prática para arrays de tamanho até 10^5: {1, 4, 10, 23, 57, 132, 301, 701, 1750} (Marcin Ciura, Best Increments for the Average Case of Shellsort, 13th International Symposium on Fundamentals of Computation Theory, LNCS 2001; Vol. 2138).