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<T>(T[] a) where T : IComparable
    {
        for (int i = 0; i < 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 < a.Length; j++)
            {
                if (Less(a[j], a[min]))
                {
                    min = j;
                }
                else if (a.Length < j + 1)
                {

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

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

            h = h / 3;
        }
    }

    public void SelectionSort<T>(T[] a) where T : IComparable
    { // Sort a[] into increasing order.
        int n = a.Length;  // array length
        for (int i = 0; i < 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 < n; j++)
                if (Less(a[j], a[min])) min = j;
            Exch(a, i, min);
            Show(a);
        }
    }

    private static void Exch<T>(T[] a, int i, int j) where T : IComparable
    {
        T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public void Show<T>(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) < 0;
    }

    public bool IsSorted(IComparable[] a)
    { // Test whether the array entries are in order.
        for (int i = 1; i < 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(n3)

$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 <– probably accessing the raw stream would be even faster if needs be.

You should prefer the generic IComparable<T> to IComparable:

public static void InsertionSort<T>(T[] a) where T : IComparable<T>

public static void ShellSort<T>(T[] a) where T : IComparable<T>

public static void SelectionSort<T>(T[] a) where T : IComparable<T>

Note that we don’t need a constraint on T for Exch:

private static void Exch<T>(T[] a, int i, int j)

While we’re at it, Swap or Exchange would be a better name for Exch.

We also don’t need a constraint for Show, which can be written more simply as

public static void Show<T>(T[] a)
{
    Console.WriteLine(string.Join(" ", a));
}

Finally, we have

private static bool Less<T>(T v, T w) where T : IComparable<T>

public static bool IsSorted<T>(T[] a) where T : IComparable<T>

On my machine, these changes reduced the running time of ShellSort (not calling Show) on an array of 1,000,000 random ints from ~2.6s to ~1s (Mono 3.10.0, Debug x86).