希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由希尔在 1959 年所发表的论文“A high-speed sorting procedure”中所描述。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1961年，IBM 公司的女程序员 Marlene Metzner Norton（玛琳·梅茨纳·诺顿）首次使用 FORTRAN 语言编程实现了希尔排序算法。在其程序中使用了一种简易有效的方法设置希尔排序所需的增量序列：第一个增量取待排序记录个数的一半，然后逐次减半，最后一个增量为 1。该算法后来被称为 Shell-Metzner 算法，Metzner 本人在2003年的一封电子邮件中说道：“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”