Fast List<String> Sort in C#

namespace Sorting.SedgewickSort
{
    public static class Sedgewick
    {

        static char CharOrNull(string s, int pos)
        {
            if (pos >= s.Length)
                return (char)0;
            return s[pos];
        }

        static int medianOf3(string[] x, int a, int b, int c, int depth)
        {
            char va, vb, vc;
            if ((va = CharOrNull(x[a], depth)) == (vb = CharOrNull(x[b], depth)))
                return a;
            if ((vc = CharOrNull(x[c], depth)) == va || vc == vb)
                return c;
            return va < vb ?
                  (vb < vc ? b : (va < vc ? c : a))
                : (vb > vc ? b : (va < vc ? a : c));
        }

        //Pathological case is: strings with long common prefixes will
        //          cause long running times
        public static void InsertionSort(string[] x, int a, int n, int depth)
        {
            int pi;
            int pj;
            for (pi = a + 1; --n > 0; pi++)
            {
                for (pj = pi; pj > a; pj--)
                {
                    string s = x[pj - 1];
                    string t = x[pj];
                    int d = depth;

                    int s_len = s.Length;
                    int t_len = t.Length;
                    while (d < s_len && d < t_len && s[d] == t[d]) { d++; };
                    if (d == s_len || (d < t_len && s[d] <= t[d]))
                        break;
                    int pj1 = pj - 1;
                    string tmp = x[pj]; x[pj] = x[pj1]; x[pj1] = tmp;
                }
            }
        }

        static void vecswap(string[] x, int a, int b, long n)
        {

            while (n-- > 0)
            {
                string t = x[a];
                x[a++] = x[b];
                x[b++] = t;
            }
        }


        public static string[] Sort(string[] input)
        {
            string[] copy = new string[input.Length];
            input.CopyTo(copy, 0);
            InPlaceSort(copy, 0, copy.Length, 0);
            return copy;
        }

        public static void Sort(ref string[] inout)
        {
          InPlaceSort(inout, 0, inout.Length, 0);
        }


        static void InPlaceSort(string[] x, int a, int n, int depth)
        {
            char partval;
            int d, r;
            int pa;
            int pb;
            int pc;
            int pd;
            int pl;
            int pm;
            int pn;
            string t;
            if (n < 10)
            {
                InsertionSort(x, a, n, depth);
                return;
            }
            pl = a;
            //pm = a + (n / 2); 
            pm = a + (n >> 1); 
            pn = a + (n - 1);
            if (n > 30)
            { 
                // On big arrays, pseudomedian of 9
                //d = (n / 8);
                d = (n >> 3);
                pl = medianOf3(x, pl, pl + d, pl + 2 * d, depth);
                pm = medianOf3(x, pm - d, pm, pm + d, depth);
                pn = medianOf3(x, pn - 2 * d, pn - d, pn, depth);
            }
            pm = medianOf3(x, pl, pm, pn, depth);

            { t = x[a]; x[a] = x[pm]; x[pm] = t; }

            pa = pb = a + 1;
            pc = pd = a + n - 1;

            partval = CharOrNull(x[a], depth);
            int len = x[a].Length;
            bool empty = (len == depth);
            
            for (; ; )
            {
                while (pb <= pc && (r = (empty ? (x[pb].Length - depth) : ((depth == x[pb].Length) ? -1 : (x[pb][depth] - partval)))) <= 0)  
                {
                    if (r == 0)
                    {
                        //swap(pa, pb);
                        { t = x[pa]; x[pa] = x[pb]; x[pb] = t; }
                        pa++;
                    }
                    pb++;
                }
                while (pb <= pc && (r = (empty ? (x[pc].Length - depth) : ((depth == x[pc].Length) ? -1 : (x[pc][depth] - partval)))) >= 0)
                {
                    if (r == 0)
                    {   //swap(pc, pd); 
                        { t = x[pc]; x[pc] = x[pd]; x[pd] = t; }
                        pd--;
                    }
                    pc--;
                }
                if (pb > pc) break;

                //swap(pb, pc);
                { t = x[pb]; x[pb] = x[pc]; x[pc] = t; }
                pb++;
                pc--;
            }
            
            pn = a + n;
            if (pa - a < pb - pa)
            {
                r = (pa - a);
            }
            else
            {
                r = (pb - pa);
            }

            //swapping pointers to strings
            vecswap(x, a, pb - r, r);
            if (pd - pc < pn - pd - 1) { r = pd - pc; } else { r = pn - pd - 1; }
            vecswap(x, pb, pn - r, r);
            r = pb - pa;
            if (pa - a + pn - pd - 1 > 1 && x[a + r].Length > depth) //by definition x[a + r] has at least one element
                InPlaceSort(x, a + r, pa - a + pn - pd - 1, depth + 1);
            if (r > 1)
                InPlaceSort(x, a, r, depth);
            if ((r = pd - pc) > 1)
                InPlaceSort(x, a + n - r, r, depth);
        }
    }
}