Shell Sort

Donald Shell, 1959

Invented by Donald Shell in 1959, Shell Sort improves on insertion sort by comparing elements that are far apart before finishing with nearby comparisons. It starts with a large gap (typically n/2) and performs gapped insertion sort passes, halving the gap each time until it reaches 1. This pre-sorting of distant elements dramatically reduces the total number of shifts needed. The visualization shows comparing pairs in gold, moved elements in coral, and the current gap value, illustrating how the array becomes increasingly ordered with each shrinking gap.