Does anyone have any insight in the computational complexity of the two solutions?

The shell script sorts all the words (and then all the counts), so has complexity at least O(n log n) in the number of words.

It seems to me an optimal solution could be faster, and I wonder what Knuth implemented.