Shell Sort in C#

Have you ever needed to sort a list of items, but didn’t want to use the built-in sorting function? If so, you may be interested in learning about Shell Sort, which is similar to insertion sort but uses a different approach to sorting. In this article, we’ll take a look at how shell sort works and how we can implement it in C#. We’ll also compare it to other sorting algorithms and analyze its time and space complexity.

Let’s dive in.

What is Shell Sort?

This algorithm was created by Donald Shell in 1959. It works based on the premise that sorting further elements first effectively reduces the interval between the elements that still need to undergo the sorting process. This makes the shell sort algorithm work in the same way as a generalized version of the insertion sort algorithm. 

The algorithm sorts elements at a specific interval first and reduces that interval gradually until it is equal to one. It supports different interval selection strategies such as: 

• Shell’s original sequence (N/2, N/4, …, 1), where N is the length of the array
• Knuth’s sequence: 1, 4, 13, …, (3n – 1) / 2
• Sedgewick’s sequence: 1, 8, 23, 77, 281…
• Hibbard’s sequence: 1, 3, 7, 15, 31, 63…

The algorithm may perform differently depending on the interval strategy in use but to keep this article simple, we are going to use Shell’s original sequence. 

Let’s take a deep dive and learn how shell sort works. 

How Does Shell Sort Algorithm Work?

Let’s look at an example of how shell sort works. We will use the following set of numbers:

int[] array = {34, 31, 39, 9, 15, 19, 26, 44};

When using Shell’s original sequence, we are going to start from N/2, with N being the array’s length (8).

Iteration One

We compare and swap the elements lying at the interval of 4. For example, the element at index zero gets compared with the element at index three in the array. 

With that in mind, at the interval of 4, here are the sublists that we have: {34, 15}, {31, 19}, {39, 26}, {9, 44}

Next, we are going to compare the elements in these sublists and swap their positions in the original array accordingly:

15, 19, 26, 9, 34, 31, 39, 44

Here, we can see that some elements swap their positions in the original array after the first iteration. 

Iteration Two

We set the interval to 2 i.e. N/4. These are the conceptual subarrays that we are going to sort next: {15, 26, 34, 39} and {19, 9, 31, 44}.

Once more, we are going to compare these elements and update their positions on the original array, which becomes:

15, 9, 26, 19, 34, 31, 39, 44

Final Iteration

The interval will be equal to 1 (N/8 = 1). We are going to use insertion sort to complete the sorting process. 

Assuming 15 is a sorted list of the first item, we are going to compare 15 with 9. Since 9 is less than 15, we swap their positions and the array becomes:

9, 15, 26, 19, 34, 31, 39, 44

15 is not greater than 26 while 19 is less than 26 so, we swap their positions, and the array becomes:

9, 15, 19, 26, 34, 31, 39, 44

26 is less than 34 but 31 is less than 34, so we swap their positions to complete the sorting process: 

9, 15, 19, 26, 31, 34, 39, 44

Let’s learn how to implement the shell sort algorithm in C#.

How to Implement Shell Sort in C#?

Let’s write a function ShellSort() that takes an array and its size as inputs and returns a sorted list of elements:

public int[] ShellSort(int[] array, int size, string arrayName)
{
    for (int interval = size / 2; interval > 0; interval /= 2)
    {
        for (int i = interval; i < size; i++)
        {
            var currentKey = array[i];
            var k = i;

            while (k >= interval && array[k - interval] > currentKey)
            {
                array[k] = array[k - interval];
                k -= interval;
            }

            array[k] = currentKey;
        }
    }

    return array;
}

The function implements the shell sort algorithm by using Shell’s original sequence as the outer loop keeps subdividing the gap by two until it gets equal to one. For every gap interval, the function uses insertion sort to compare and swap array elements until the array is sorted. 

Finally, we can verify that the CountingSort() method sorts a given unsorted array accurately:

var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new ShellSortMethods();

var sortedArray = sortFunction.ShellSort(array, array.Length, string.Empty);

Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(sortedArray, expected);

Space and Time Complexity of Shell Sort Algorithm

The space complexity of the algorithm is O(n), with n being the size of the array. On top of that, the algorithm takes O(1) as auxiliary space, which means, it does not require any extra space to run.

Best-Case Time Complexity

The shell sort algorithm encounters its best-case time complexity scenario when it encounters an array that is already sorted. The number of comparisons for every interval is equal to the size of the array. Therefore, the algorithm has a best-case time complexity of O(n log n).

Average-Case Time Complexity

The shell sort algorithm has an average-case time complexity of O(n log n) just as its best-case time complexity. This scenario occurs when we use different intervals and it depends on the interval chosen by the programmer. 

Worst-Case Time Complexity

Shell sort has a worst-case time complexity of O(n²). This scenario occurs when we select the worst known gap sequence while selecting the best known worst-case gap sequence makes the algorithm have a worst-case time complexity of O(n log² n). The gap sequence we use in this article operates in quadratic time making it have a time complexity of O(n²). 

We can simulate worst-case time complexity when using Shell’s original sequence when we put the smallest elements in odd positions and the largest elements in even positions. For example, when we try to sort an array such as  2, 11, 4, 12, 6, 13, 8, 14 none of the passes (N/2, N/4, …, 2) rearrange the elements. The algorithm will swap the elements in the last pass when the gap is 1, which would force the algorithm to perform n² comparisons.

Advantages of Shell Sort Algorithm

The shell sort algorithm has several advantages, including being efficient when sorting medium size arrays.

Besides that, the algorithm does not require any extra space to run unlike sorting algorithms such as merge sort.

Shell sort performs better than other sorting algorithms such as insertion sort and bubble sort.

Finally, it is adaptive, as its runtime reduces when it encounters an array that is almost sorted. 

Disadvantages of Shell Sort Algorithm

The shell sort algorithm can be less efficient than other sorting algorithms for large data sets such as merge sort and quicksort. Additionally, the algorithm is not stable, meaning that it may not preserve the order of elements with equal keys just like quicksort.

Performance Tests

Let’s test how long the algorithm takes for it to sort three arrays that have 2,000,000 elements each. To help us complete these tests, we are going to implement two methods. 

First, let’s write a method to generate a set of random array elements:

public static int[] CreateRandomArray(int size, int lower, int upper)
{
    var array = new int[size];
    var rand = new Random();

    for (int i = 0; i < size; i++)
        array[i] = rand.Next(lower, upper);

    return array;
}

The CreateRandomArray() the method takes three integers size, lower and upper. Using the inbuilt Random class, we generate integer values between lower and upper that we’re going to put into the array.

Next, we are going to simulate the best-case time complexity scenario by defining a method CreateSortedArray() that returns a sorted array: 

public static int[] CreateSortedArray(int size)
{
    var array = new int[size];

    for (int i = 0; i < size; i++)
        array[i] = i;

    return array;
}

To simulate the worst-case time complexity scenario, we are going to use  CreateRandomArray() we have but tweak it in such a way that we have small elements in odd positions and larger elements in even positions in the array:

public static int[] CreateImbalancedArray(int size, int lower, int upper)
{
    var array = new int[size];
    var rand = new Random();

    for (int i = 0; i < size; i++) 
    {
        if ((i % 2) == 0)
        {
            array[i] = rand.Next(upper/2, upper);
        }
        else 
        {
            array[i] = rand.Next(lower, 1000);
        }    
    }

    return array;
}

Here, we see that we place numbers random numbers between lower and 1000 in odd positions in the array and larger elements between upper/2 and upper in even positions of the array. 

Sample Array Objects

We are going to create an object that holds different arrays that have random and sorted values:

public IEnumerable<object[]> SampleArrays()
{
    yield return new object[] { CreateSortedArray(2000000), 2000000, "Best Case" };
    yield return new object[] { CreateRandomArray(2000000, 1, 2000000), 2000000, "Average Case" };
    yield return new object[] { CreateImbalancedArray(2000000, 1, 2000000), 2000000, "Worst Case" };
}

Each object entry has two values: an integer array e.g.  CreateRandomArray(2000000, 1, 2000000) and a string object storing the name of that array (“Average Case”). This object sorts random numbers between 1 and 2,000,000, which ensures that the array elements are distributed uniformly within the range. 

On the other hand, the last object invokes the CreateImbalancedArray() function, which returns an array that has small array elements in odd positions and larger elements in even positions.

Sample Test Results

Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:

|    Method |          array |    size |    arrayName |     Mean |    Error |   StdDev |
|---------- |--------------- |-------- |------------- |---------:|---------:|---------:|
| ShellSort | Int32[2000000] | 2000000 | Average Case | 86.72 ms | 1.718 ms | 4.465 ms |
| ShellSort | Int32[2000000] | 2000000 |    Best Case | 85.88 ms | 0.496 ms | 0.440 ms |
| ShellSort | Int32[2000000] | 2000000 |   Worst Case | 86.80 ms | 1.734 ms | 4.052 ms |

As we can see, despite the algorithm sorting 2,000,000 elements, they have different runtimes. 

The shell sort algorithm encounters its best-case time complexity scenario as the array encounters a sorted list of elements. Additionally, we can see that shell sort’s average-case time complexity is achieved when we randomly select values within the range. On the other hand, when we place small array elements in odd positions and larger elements in even positions the algorithm encounters its worst-case time complexity.

The results are almost similar as we use the same gap sequence (Shell’s original sequence). The worst-case time complexity’s runtime is about 0.08ms slower than the average-case time complexity’s runtime. On the other hand, the average-case runtime is about 0.84ms slower than the best-case runtime. Please note that these runtimes may change depending on the number of elements and the computing resources available. 

Conclusion

In summary, shell sort uses this working principle:

1. The algorithm DETERMINEs the size of the intervals going to be used
2. DIVIDE the array into conceptual subarrays using the elements whose distance is determined by the interval
3. SORT the conceptual subarrays in place
4. SHORTEN the gap by N/2 (Shell’s sequence)
5. REPEAT the steps above until the interval is equal to 1 and use insertion sort to complete the sorting process

In this article, we have learned how shell sort in C# works and its time and space complexity.