Shell sort is a generalization of insertion sort that sorts elements far apart before sorting adjacent ones. Invented by Donald Shell in 1959, it repeatedly applies insertion sort on sublists of decreasing “gap” sizes until the gap reaches 1 — at which point one final insertion sort on the nearly-sorted array runs in near-linear time. …