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