Řazení vkládáním je pomalé, když prvky v řazené posloupnosti jsou vzdálené od své správné pozice v seřazené posloupnosti, protože jsou vyměňovány jenom se svým sousedem.
Mějme posloupnost
4 2 7 6 3 9 8 5 1 0
Vložíme-li postupně prvky 2, 7, ... až 5 do uspořádaných podposloupností před nimi, budeme mít posloupnost
2 3 4 5 6 7 8 9 1 0
Prvky 0 a 1 nyní pro dosažení správné pozice musí „projít“ téměř celou posloupnost.
Řazení haldou dosáhlo snížení časové náročnosti tím, že operace výběru největšího z k neseřazených prvků trvá zkrácením počtu procházených prvků log2k, díky jejich organizaci v haldě.
Myšlenka D. Shella z roku 1959 je podobná pro vkládání. Aby jsme zkrátili cestu prvku ke správné pozici, seřadíme vkládáním prvky vzdálené h. Celá řazená posloupnost je nyní organizována jako h podposloupností začínajících prvky na pozicích 0, 1, ..., h-1, každá obsahující prvky vzdálené h.
Pro náš příklad a h = 4 je situace v horní části obr.
, kde jsou podposloupnosti v jednotlivých řádcích vyznačeny tučně. Aplikujeme-li na tyto podposloupnosti algoritmus řazení vkládáním, cesta prvků 1 a 0 k jejich správné pozici se podstatně zkrátí. Ve spodní části obr. jsou úpravy uvedené posloupnosti po jednotlivých krocích pro každou podposloupnost.
Obecně po seřazení všech podposloupností s prvky vzdálenými h získáme posloupnost, které říkáme, že je h-seřazena. V našem příkladě je poslední posloupnost na obr. 4-seřazena.
Volbou dostatečně velkého h vzhledem k počtu řazených prvků, tak můžeme posunout prvky posloupnosti na velkou vzdálenost. Dále postup opakujeme pro klesající posloupnost hodnot h. Je-li poslední hodnota 1 jistě získáme seřazenou posloupnost.
Otázka je jaká má být posloupnost hodnot h. Shell navrhnul pro posloupnost s n prvky začít s n /2 a postupně tuto hodnotu půlit dokud nedosáhne 1. Vzdálenost mezi řazenými prvky klesá geometricky, tedy jejich počet je log2 n. Na druhé straně, v tomto případě prvky na sudých pozicích nejsou porovnány s prvky na lichých pozicích až do posledního průchodu.
Knuth navrhnul zvolit začáteční vzdálenost přibližně třetinovou a postupně ji dělit třemi. Přesněji, posloupnost vzdáleností jsou prvky posloupnosti
1 4 13 40 121 364 1093 3280 ...
což jsou čísla tvaru 3i + 1, i = 0, 1, ... .
Nyní bychom mohli napsat program, který by pro postupně se zmenšující vzdálenosti řazených prvků vždycky seřadil všechny podposloupnosti tak, jak jsme to udělali v našem příkladě. Jelikož pro danou vzdálenost jsou jednotlivé podposloupnosti navzájem nezávislé, můžeme postupovat tak, že napřed v první vložíme druhý prvek na správné místo, potom druhý prvek ve druhé, atd. Po vložení druhého prvku poslední podposloupnosti pokračujeme vložením třetích prvků první pospouslopnosti atd. Tomu odpovídají postupně následující tvary řazené posloupnosti.
3 2 7 6 4 9 8 5 1 0
3 2 7 6 4 9 8 5 1 0
3 2 7 6 4 9 8 5 1 0
3 2 7 5 4 9 8 6 1 0
1 2 7 5 3 9 8 6 4 0
1 0 7 5 3 2 8 6 4 9
Dostali jsme 4-seřazenou posloupnost stejnou jako původním postupem na obr..
Algoritmus Shellova řazení pro posloupnost vzdáleností navrnuté Knuthem je na obr.
.
Čas výpočtu algoritmu Shellovým řazením závisí, jak jsme již naznačili, na výběru posloupnosti vzdáleností. Obecné řešení není dosud známo. Není ani známa dokazatelně nejlepší posloupnost vzdáleností i když některé posloupnosti v praktických aplikacích se dobře osvědčují. Knuth zjistil, že n1.25 je dobré omezení.
Shellovo řazení je nejjednodušší efektivní řazení (i když ne nejefektivnější) a může být proto první volbou v praktických aplikacích, zejména pro rozsah řazených posloupností v řádu do desítek tisíc prvků. Až když Shellovo řazení není postačující, sáhneme k efektivnějším, ale složitějším, algoritmům. Shellův algoritmus je hezkým příkladem jednoduchého algoritmu, jehož analýza je velice složitá.