Correct answer to Google's CEO question is LSD radix sort.

LSD radix sort runs in O(N + R) time (2W (N + R) to be exact) while traditional IComparable-based sorts such as QuickSort or MergeSort are N(Log N) lower-bound.

Here is my take on the solution:

public static void LsdStringNumberSort(string[] a, int w)  
{
    int radix = 10;
    int n = a.Length;
    string[] aux = new string[n];

    for (int d = w - 1; d >= 0; d--)
    {
        int[] count = new int[radix + 1];
        for (int i = 0; i < n; i++)
        {            
            count[CharToInt(a[i][d]) + 1]++;
        }
        for (int r = 0; r < radix; r++)
        {
            count[r + 1] += count[r];
        }
        for (int i = 0; i < n; i++)
        {            
          aux[count[CharToInt(a[i][d])]++] = a[i];
        }
        for (int i = 0; i < n; i++)
        {
            a[i] = aux[i];
        }
     }   
}

In my tests, however this code runs no faster than Array.Sort, both take 831 ms for 1 million numbers.

I am not yet sure why it cannot beat Array.Sort, but here is the complete code