Średnia liczba porównań wykonywanych podczas sortowania z trzema przebiegami gdzie i są względnie pierwsze wynosi w pierwszym przebiegu, w drugim przebiegu i w trzecim przebiegu. Skomplikowana funkcja z ostatniego wzoru jest asymptotycznie równa W szczególności, gdy a średni czas sortowania jest rzędu
Na podstawie doświadczeń odgadnięto, że z ciągami Hibbarda i Knutha algorytm działa w średnim czasie rzędu , a z ciągiem Gonneta i Baezy-Yatesa wykonuje średnio przesunięć elementów. Aproksymacje średniej liczby operacji czynione kiedyś dla innych ciągów zawodzą, gdy sortowane tablice liczą miliony elementów.
Poniższy wykres przedstawia średnią liczbę porównań elementów w różnych wariantach sortowania Shella, dzieloną przez teoretyczne minimum, czyli przy czym do ciągu 1, 4, 10, 23, 57, 132, 301, 701 dodano dalsze wyrazy zgodnie ze wzorem
center
Korzystając z teorii złożoności Kołmogorowa, Jiang, Li i Vitányi udowodnili następujące dolne ograniczenia na rząd średniej liczby operacji w -przebiegowym sortowaniu Shella: przy i przy . Zatem algorytm ten ma szanse działać w średnim czasie rosnącym asymptotycznie jak tylko z ciągami o liczbie odstępów rosnącej proporcjonalnie do logarytmu długości sortowanych tablic.