Nhược điểm của thuật toán Insertion Sort khi ta phải chèn một phần tử khoá vào vị trí gần đầu dãy. Để khắc phục nhược điểm này, ta có thể sử dụng thuật toán chèn với độ dài bước giảm dần, được đưa ra bởi D.L.Shell. Có thể vì vậy mà thuật toán có tên gọi là ShellSort.

Ý tưởng của thuật toán là chia dãy khoá k[1..n] thành h dãy con với \(1 \leq h \leq n\). Khi đó ta có các dãy con như sau:
Dãy con 1: k[1], k[1 + h], k[1 + 2h], …
Dãy con 2: k[2], k[2 + h], k[2 + 2h], …
…
Dãy con h: k[h], k[h + h], k[h + 2h], …

Chúng ta áp dụng thuật toán Insertion Sort trên từng dãy con độc lập để làm mịn dầy dãy khoá chính. Rồi làm tương tự với bước h giảm dần bằng h div 2. Cho tới khi h = 1 thì ta được một dãy khoá sắp xếp. ShellSort hoạt động nhanh và dễ cài đặt, tuy nhiên việc đánh giá độ phức tạp thuật toán là tương đối khó, chúng ta chỉ thừa nhận kết quả (bạn đọc có thể tìm hiểu thêm).

Dưới đây là cách cài đặt của thuật toán ShellSort, mọi người có thể theo dõi.

#include <iostream>

using namespace std;

int arr[5] = {1, 5, 4, 2, 3};
int n = 5;
void print();
void shellSort();

int main() {
    shellSort();
    print();
}

void shellSort() {
    int i, j, tmp, h;
    h = n / 2;
    while (h != 0) {
        for (i = h; i < n; i ++) {
            // sắp xếp chèn trên dãy con a[i - h], a[i], a[i + h], a[i + 2h], ...
            tmp = arr[i];
            j = i - h;
            while (j >= 0 and arr[j] > tmp) {
                arr[j + h] = arr[j];
                j = j - h;
            }
            arr[j + h] = tmp;
        }
        h = h / 2;
    }
}

void print() {
    for (int i = 0; i < n; i ++) {
        cout << arr[i] << '\t';
    }
    cout << endl;
}

Kết quả khi chạy chương trình trên sẽ như sau:

1	2	3	4	5