C# Shell Sort
last modified November 6, 2026
In this article we implement the Shell sort algorithm in C#. We trace the gap passes, write a generic version, and compare several gap sequences.
Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.
Shell sort algorithm
Shell sort, published by Donald Shell in 1959, is a generalization of insertion sort. Insertion sort moves an element only one position per step, so an element far from its final position needs many steps. Shell sort first sorts elements that are a gap apart. Elements jump over long distances, and the array quickly becomes roughly sorted. The gap shrinks with each pass, and the last pass with gap 1 is an ordinary insertion sort on an almost sorted array.
| Property | Value |
|---|---|
| Worst case | depends on the gap sequence, O(n²) for halving gaps |
| Average case | no exact formula; roughly O(n1.25) to O(n1.5) for good sequences |
| Extra memory | O(1), sorts in place |
| Stable | no |
C# Shell sort example
The first example uses the original sequence, which starts at half the array length and halves the gap in each pass.
int[] nums = [23, 12, 1, 8, 34, 54, 2, 3, 17, 9];
ShellSort(nums);
Console.WriteLine(string.Join(" ", nums));
static void ShellSort(int[] arr)
{
for (int gap = arr.Length / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < arr.Length; i++)
{
int key = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > key)
{
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
}
The method sorts the array in place.
for (int gap = arr.Length / 2; gap > 0; gap /= 2)
For ten elements, the gaps are 5, 2, and 1.
while (j >= gap && arr[j - gap] > key)
{
arr[j] = arr[j - gap];
j -= gap;
}
This is the insertion sort loop with the step of gap instead of 1.
Each pass sorts the subsequences of elements that are gap
positions apart. Such an array is called gap-sorted.
$ dotnet run 1 2 3 8 9 12 17 23 34 54
Shell sort step by step
The next example prints the array and the number of shifts after each pass.
int[] nums = [35, 33, 42, 10, 14, 19, 27, 44, 26, 31];
ShellSort(nums);
static void ShellSort(int[] arr)
{
for (int gap = arr.Length / 2; gap > 0; gap /= 2)
{
int shifts = 0;
for (int i = gap; i < arr.Length; i++)
{
int key = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > key)
{
arr[j] = arr[j - gap];
j -= gap;
shifts++;
}
arr[j] = key;
}
Console.WriteLine($"gap {gap}: {string.Join(" ", arr)} ({shifts} shifts)");
}
}
In the first pass, the elements 5 positions apart are compared, for instance 35 and 19. The second pass sorts the elements at even and at odd positions separately. The final insertion sort needs only 2 shifts, because the array is almost sorted. The three passes make 12 shifts in total; plain insertion sort needs 22 shifts for this input.
$ dotnet run gap 5: 19 27 42 10 14 35 33 44 26 31 (2 shifts) gap 2: 14 10 19 27 26 31 33 35 42 44 (8 shifts) gap 1: 10 14 19 26 27 31 33 35 42 44 (2 shifts)
Generic Shell sort
The generic version takes an IComparer<T>.
string[] cities = ["Paris", "Oslo", "Bern", "Rome", "Vienna", "Madrid", "Prague", "Lisbon"];
ShellSort(cities, StringComparer.Ordinal);
Console.WriteLine(string.Join(" ", cities));
ShellSort(cities, Comparer<string>.Create((a, b) => b.Length != a.Length
? b.Length.CompareTo(a.Length) : string.CompareOrdinal(a, b)));
Console.WriteLine(string.Join(" ", cities));
static void ShellSort<T>(T[] arr, IComparer<T> comparer)
{
for (int gap = arr.Length / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < arr.Length; i++)
{
T key = arr[i];
int j = i;
while (j >= gap && comparer.Compare(arr[j - gap], key) > 0)
{
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
}
We sort city names alphabetically, and then by length in descending order.
ShellSort(cities, Comparer<string>.Create((a, b) => b.Length != a.Length
? b.Length.CompareTo(a.Length) : string.CompareOrdinal(a, b)));
Names of equal length are compared alphabetically. Shell sort is not stable, so we cannot rely on the alphabetical order from the previous sort to be preserved. The comparer must define the order of equal-length names explicitly.
$ dotnet run Bern Lisbon Madrid Oslo Paris Prague Rome Vienna Lisbon Madrid Prague Vienna Paris Bern Oslo Rome
Gap sequences
The choice of the gap sequence has a large effect on the speed. The halving sequence is simple, but it compares elements at even and odd positions only in the last pass. Better sequences have been found:
- Knuth (1973): 1, 4, 13, 40, 121, ..., computed as
3h + 1 - Ciura (2001): 1, 4, 10, 23, 57, 132, 301, 701, found by experiments; it is usually extended by multiplying the last gap by 2.25
The following example sorts 200,000 random integers with each sequence.
#:property PublishAot=false
using System.Diagnostics;
const int N = 200_000;
var rnd = new Random(17);
int[] data = [.. Enumerable.Range(0, N).Select(_ => rnd.Next(1_000_000))];
Measure("Shell (n/2, n/4, ...)", ShellGaps(N));
Measure("Knuth (1, 4, 13, ...)", KnuthGaps(N));
Measure("Ciura (1, 4, 10, ...)", CiuraGaps(N));
int[] copy = [.. data];
var sw = Stopwatch.StartNew();
Array.Sort(copy);
Console.WriteLine($"{"Array.Sort",-22} {sw.Elapsed.TotalMilliseconds,8:F2} ms");
void Measure(string label, int[] gaps)
{
int[] copy = [.. data];
var sw = Stopwatch.StartNew();
long comparisons = ShellSort(copy, gaps);
Console.WriteLine($"{label,-22} {sw.Elapsed.TotalMilliseconds,8:F2} ms {comparisons,12:N0} comparisons");
}
static int[] ShellGaps(int n)
{
List<int> gaps = [];
for (int gap = n / 2; gap > 0; gap /= 2) gaps.Add(gap);
return [.. gaps];
}
static int[] KnuthGaps(int n)
{
List<int> gaps = [];
for (int gap = 1; gap < n / 3; gap = 3 * gap + 1) gaps.Add(gap);
gaps.Reverse();
return [.. gaps];
}
static int[] CiuraGaps(int n)
{
List<int> gaps = [1, 4, 10, 23, 57, 132, 301, 701];
while (gaps[^1] * 9 / 4 < n) gaps.Add(gaps[^1] * 9 / 4);
gaps.Reverse();
return [.. gaps];
}
static long ShellSort(int[] arr, int[] gaps)
{
long comparisons = 0;
foreach (int gap in gaps)
{
for (int i = gap; i < arr.Length; i++)
{
int key = arr[i];
int j = i;
while (j >= gap)
{
comparisons++;
if (arr[j - gap] <= key) break;
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = key;
}
}
return comparisons;
}
The sequences are generated in ascending order and reversed, because Shell sort uses the largest gap first.
for (int gap = 1; gap < n / 3; gap = 3 * gap + 1) gaps.Add(gap);
Knuth recommends stopping when the gap reaches a third of the array length.
while (gaps[^1] * 9 / 4 < n) gaps.Add(gaps[^1] * 9 / 4);
The Ciura sequence is extended with integer arithmetic; gaps[^1]
is the last element of the list.
comparisons++; if (arr[j - gap] <= key) break;
We count every comparison, including the one that stops the inner loop.
#:property PublishAot=false
File-based apps are published with Native AOT by default. The directive turns this off, so the release build does not pull in the AOT compiler package.
We run the program in the Release configuration. The comparison counts do not
depend on the machine, unlike the times. The Ciura sequence needs about half
as many comparisons as the halving sequence. All variants are much faster than
an O(n²) algorithm would be, but Array.Sort still wins.
$ dotnet run -c Release gaps.cs Shell (n/2, n/4, ...) 29.25 ms 10,022,025 comparisons Knuth (1, 4, 13, ...) 24.16 ms 9,534,804 comparisons Ciura (1, 4, 10, ...) 24.22 ms 5,490,129 comparisons Array.Sort 12.56 ms
Source
In this article we have implemented the Shell sort algorithm in C#.
Other sorting algorithms in C#:
- Bubble sort
- Selection sort
- Insertion sort
- Merge sort
- Quick sort
- Heap sort
- Counting sort
- Radix sort
- Bucket sort
Author
List all C# tutorials.