希尔排序（ShellSort）也称增量递减排序算法，即跨多步版的InsertionSort，是InsertionSort基础上的改进版。InsertionSort可以看作ShellSort中gap=1的特例。希尔排序是非稳定排序算法。
希尔排序通过将全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
ShellSort的关键点在于gap序列的设计。
每一轮报数，队列中123123…（gap=3）地报数,所有报1的人组成一组，在原队列中进行插入排序，其他组类似。
报数分为好几轮，每轮gap值减小一次，每一轮都使序列渐进有序化，直到最后一轮gap=1，即为原始InsertionSort。从这个意义上说，ShellSort是加了预处理的InsertionSort。
假设有这样一组数
如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
然后我们对每列进行排序：
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
排序之后变为：
最后以1步长进行排序（此时就是简单的插入排序了）。
ShellSort的复杂度分析非常复杂，不同gap序列的设计对应不同的复杂度。
最坏时间复杂度：根据步长序列的不同而不同。已知最好的： O(n (logn) ^2)
最优时间复杂度: O(n)
平均时间复杂度：根据步长序列的不同而不同。
最坏空间复杂度： O(n)
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。
Donald Shell最初建议步长选择为 n/2 并且对步长取半直到步长达到1。虽然这样取可以比 O(n^2)类的算法更好，但这样仍然有减少平均时间和最差时间的余地。
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…)。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。