希爾排序，以其發明者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 }