ここでは高速に処理ができるアルゴリズムを紹介する。ここで高速と呼んでいるものは、Ｏ（ｎｌｏｇｎ）に分類できるものである。
入力データ 45 56 13 43 95 18 7 68 ステップ１分割の幅をｓｋｉｐ＝４とし、上記データをいくつかのブロックに分割する。
45 56 13 43 95 18 7 68 ^ ^ ^ ^ ^ ^ ^ ^ | | | | | | | | B1 B2 B3 B4 B1 B2 B3 B4 <--- 便宜上ブロックに名前を付けた このブロック内で並べ替えをおこなう。 Ｂ１ブロック 45 95 ----> 45 95 Ｂ２ブロック 56 18 ----> 18 56 Ｂ３ブロック 13 7 ----> 7 13 Ｂ４ブロック 43 68 ----> 43 68 よって、 45 18 7 43 95 56 13 68 となる。ステップ２ 分割の幅を１／２にする。ｓｋｉｐ＝２としてブロックに分割する。
45 18 7 43 95 56 13 68
^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | |
B1 B2 B1 B2 B1 B2 B1 B2
このブロック内で並べ替えを行なう。
Ｂ１ブロック 45 7 95 13 ----> 7 13 45 95
Ｂ２ブロック 18 43 56 68 ----> 18 43 56 68
よって、
7 18 13 43 45 56 95 68
となる。
ステップ３ 分割の幅をさらに１／２にする。ｓｋｉｐ＝１となり、全データを一つのブロック として考える。
よって、
7 13 18 43 45 56 68 95となり、並べ替えが完了する。 上記分割の幅の取り方は任意でよいが、ステップを増すごとに幅が減少していなければならない。最後のステップでは、ｓｋｉｐ＝１として必ず全データを一つのブロックとして並べ替えを行なわなければならない。
1: void ShellSort(int data[], int n) {
2: int i, skip;
3:
4: skip = n / 2;
5: while( skip > 0 ) {
6: Insertionsort( data, skip, n );
7: skip = skip / 2;
8: }
9: }
10:
11: void Insertionsort(int data[], int skip, int n) {
12: int tmp, i, j;
13:
14: for (i=skip; i < n; i=i+skip)
15: for (j=i-skip; j >= 0; j=j-skip)
16: if(data[j] > data[j+skip]) {
17: tmp = data[j];
18: data[j] = data[j+skip];
19: data[j+skip] = tmp;
20: }
21: }
１１〜２１は、単純挿入法のメソッドである。単純挿入ソートで紹介したメソッドと別なものをここでは紹介した。一見バブルソートに外観が似ているが、基本的な考え方は単純挿入法であることに注意しよう。ただし、変数ｓｋｉｐを用いて１次元的なデータをｓｋｉｐ個おきに取っていくことによって、ブロックに分割しているように扱っている。
上記シェルソートでは、分割の幅を１／２にして求めているが、任意でよいが、なるべく互いに素（割り切れない）の数を選ぶとよい。この幅の取り方によってデータの入れ替え回数が変わることが知られている。
Ｄ．Ｅ．Ｋｎｕｔｈは、以下のような数列で分割の幅を採用すると効率がよいことを示した。
１、４、１３、４０、１２１、．．一般的に、Ｓi+1 ＝ ３＊Ｓi ＋１, Ｓ1＝１ で得られる数列を逆順にとるものとする。これらの数値は、互いに素ではないが、より効率的であることが知られている。 次のプログラムは、上記Ｋｎｕｔｈが推奨する数列で得られた数値を分割幅に採用した例である。
1: void ShellSort(int data[], int n) {
2: int i, skip[] = {121,40,13,4,1};
3:
4: for ( i=0; i < 5; i++ )
5: Insertionsort( data, skip[i], n );
6: }
7:
8: void Insertionsort(int data[], int skip, int n) {
9: int tmp, i, j;
10:
11: for (i=skip; i < n; i=i+skip)
12: for (j=i-skip; j >= 0; j=j-skip)
13: if(data[j] > data[j+skip]) {
14: tmp = data[j];
15: data[j] = data[j+skip];
16: data[j+skip] = tmp;
17: }
18: }
シェルソートの計算時間量は、分割の幅の取り方によりＯ（ｎ＾１.２）からＯ（ｎ＾２）であることが、知られている。証明については、難しいため省略する。