Shell Sort

Shell sort is insertion sort with a head start. Plain insertion sort only moves a value one spot at a time, so something small stuck out at the far end has to crawl across the whole array. Shell sort gets around that by comparing items that sit far apart first, sorting those, then closing the gap and going again until the gap is 1 and it’s just plain insertion sort. By then everything is nearly in order, so that last pass barely has to do anything.

The gaps here are the ones Shell picked first: start at half the length and halve it each round. Big gaps shove things most of the way across for almost nothing, and each smaller gap cleans up what the last one missed. Nobody really agrees on the Big-O since it depends on the gaps you use, but this one lands between n log n and n², which beats plain insertion’s n² for basically no extra code.

Hit Play to watch it run, or use Next and Back to step one comparison at a time. Shuffle deals a fresh array, and the highlighted line shows you where the code is at each step.