Shell sort seems inefficient I am testing various sorting algorithms. Right now I am testing shell sort, insertion sort and selection sort. I ran all three algorithms on a randomly-generated list of 1000 integers. The selection sort took 41 seconds, insertion sort took 34 seconds and shell sort sort took over 3 minutes. What can I do to improve my implementation?

  public class SortAlgorithm
{
    public void InsertionSort&lt;T&gt;(T[] a) where T : IComparable
    {
        for (int i = 0; i &lt; a.Length; i++)
        { // Exchange a[i] with smallest entry in a[i+1...N).
            int min = i;  // index of minimal entr.
            for (int j = i + 1; j &lt; a.Length; j++)
            {
                if (Less(a[j], a[min]))
                {
                    min = j;
                }
                else if (a.Length &lt; j + 1)
                {

                    a[j + 1] = a[j];
                    a[j] = a[min];
                }
            }
            Show(a);
            Exch(a, i, min);
        }
    }

    public void ShellSort&lt;T&gt;(T[] a) where T : IComparable
    { // Sort a[] into increasing order.
        int N = a.Length;
        int h = 1;
        while (h &lt; N / 3)
        {
            h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ..
        }
        while (h &gt;= 1)
        { // h-sort the array.
            for (int i = h; i &lt; N; i++)
            { // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
                for (int j = i; j &gt;= h &amp;&amp; Less(a[j], a[j - h]); j -= h)
                    Exch(a, j, j - h);
                Show(a);
            }

            h = h / 3;
        }
    }

    public void SelectionSort&lt;T&gt;(T[] a) where T : IComparable
    { // Sort a[] into increasing order.
        int n = a.Length;  // array length
        for (int i = 0; i &lt; n; i++)
        { // Exchange a[i] with smallest entry in a[i+1...N).
            int min = i;  // index of minimal entr.
            for (int j = i + 1; j &lt; n; j++)
                if (Less(a[j], a[min])) min = j;
            Exch(a, i, min);
            Show(a);
        }
    }

    private static void Exch&lt;T&gt;(T[] a, int i, int j) where T : IComparable
    {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public void Show&lt;T&gt;(T[] a) where T : IComparable
    {            // Print the array, on a single line.
        foreach (T t in a)
        {
            Console.Write(t + " ");
        }
        Console.WriteLine();
    }

    private static bool Less(IComparable v, IComparable w)
    {
        return v.CompareTo(w) &lt; 0;
    }

    public bool IsSorted(IComparable[] a)
    { // Test whether the array entries are in order.
        for (int i = 1; i &lt; a.Length; i++)
            if (Less(a[i], a[i - 1])) return false;
        return true;
    }
}
Show() is probably slowing it down. It transforms your implementation into \$O(n^3)\$ and even worse increases the algorithm's time by (n*[time taken to access and write to console stream]) in the last loop. Preparing your string and printing once to the console would increase the speed, even better, printing when the list is sorted. Requesting and using resources (e.g. streams) during an expensive operation will increase execution time. You are using Console.Write &lt;-- probably accessing the raw stream would be even faster if needs be.