希尔排序，以其发明者Donald Shell的名字来命名，是最早突破时间复杂度屏障O(n²)的算法之一。希尔排序是直接插入排序的变种，它不是一种稳定的排序算法。希尔排序的原理是首先比较远距离的元素，然后递减比较距离，最终比较相邻元素。由于采用这种比较方式来排序，希尔排序有时候也被称为递减增量排序。

增量序列的不同将直接影响希尔排序的速度，因此，不方便给出希尔排序理论上的时间复杂度。 Hibbard采用的增量序列为：1, 3, 7, ..., 2k– 1，(k = 1, 2, ...)，最坏情况下的时间复杂度为O(n^3/2)，Sedgewick 建议了几种增量序列，最坏情况下的时间复杂度为O(n^4/3)，平均时间复杂度O(n^7/6)，Empirical研究发现它们的实际性能要比Hibbard的增量序列好一些，其中最好的是1, 5, 19, 41, 109, . . .，也就是说增量值要么为9*4ⁱ- 9 *2ⁱ + 1 要么为4ⁱ - 3 *2ⁱ + 1，(i = 0, 1, 2, ...)。希尔排序的空间复杂度依赖于具体实现。

以随机整数序列为例，采用Hibbard 增量序列的希尔排序过程如下表。

78 17 98 91 45 95 96 95 74 14 10 79 70 19 30 66	待排序序列
78  17 14 10 45 70 19 30 66 98 91 79 95 96 95 74	增量为7的排序结果
78 10 14 17 19 30 45 70 66 74 91 79 95 96 95 98	增量为2的排序结果
10 14 17 19 30 45 66 70 74 78 79 91 95 95 96 98	增量为1的排序结果

 1 template <typename RandomIterator, typename T, typename Compare>
 2 inline void shell_linear_insert(RandomIterator first, RandomIterator last,
 3                                 int incr, T value, Compare cmp)
 4 {
 5  for(; first > last; first -= incr)
 6    if(cmp(value, *(first - incr)))
 7      *first = *(first - incr);
 8  else
 9    break;
10  *first = value;
11 }
12 
13 // for Hibbard sequence： 1, 3, 7, 15, 31, 63, 127, 
14 // worst cast time complexity O(n^(3/2))
15 template <typename RandomIterator, typename Compare>
16 inline void shell_sort_H(RandomIterator first, RandomIterator last, Compare cmp)
17 {
18   if(last - first < 2)
19     return;
20   for(int incr = ((last - first) >> 1) - 1; incr > 1; incr = (incr >> 1) - 1)
21     for(RandomIterator i = first + (incr + 1); i < last; ++i)
22       shell_linear_insert(i, first + incr, incr, *i, cmp);
23   final_insertion_sort(first, last, cmp); // the last incremental value must be 1
24 }
25 
26 // for Sedgewick and Empirical sequence： 1, 5, 19, 41, 109, 209, 
27 // average time complexity O(n^(7/6)), worst case O(n^(4/3))
28 template <typename RandomIterator, typename Compare>
29 inline void shell_sort_S(RandomIterator first, RandomIterator last, Compare cmp)
30 {
31   long len = static_cast<int>(last - first);
32   if(len < 2)
33     return;
34 //  long arr[28];
35 //  for(long i = 0; i < 14; ++i)
36 //  {
37 //    arr[i*2] = 9*((1<<(2*i)) - (1<<i)) + 1;
38 //    arr[i*2 + 1] = ((1<<(2*(i+2))) - 3*(1<<(i+2))) + 1;
39 //  }
40   long arr[28] =
41   { 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001, 36289, 64769,
42     146305, 260609, 587521, 1045505, 2354689, 4188161,  9427969, 16764929,
43     37730305, 67084289, 150958081, 268386305, 603906049, 1073643521 };
44 
45   for(long i = 27; 0 < i; --i)
46   {
47     if(len < arr[i])
48       continue;
49     for(RandomIterator it = first + (arr[i] + 1); it < last; ++it)
50       shell_linear_insert(it, first + arr[i], arr[i], *it, cmp);
51   }
52   final_insertion_sort(first, last, cmp); // the last incremental value must be 1
53 }