Very interesting solution, and in the spirit of the original article. If I understood the snippet right, you are sorting the input sequence on the first column (the words) and then on the second one (the frequencies)

It is nevertheless "complecting": the uniq assumes the data is sorted and the columns of your data structure move together. Maybe this algorithm is already complex regardless of the implementation.

btw, this paradigm reminds me of APL

The sort is on line numbers, as aozgaa said. Again, the paradigm here - and this is designed for a different time - is that your data most definitely does not fit in RAM, so you use sort(1) to sort on disk and run your software using only constant memory. (In modern software, databases can and do sort on disk, but few programs do.)

In detail, for input "foo bar FOO qux FOO foo", we convert to

[1 foo, 2 bar, 3 foo, 4 qux, 5 foo, 6 foo]

(with newlines instead of commas, obviously), then sort by word (then line number) to

[2 bar, 1 foo, 3 foo, 5 foo, 6 foo, 4 qux]

at which point the uniq invocation gives <count> <first_line> <word>, i.e.

[1 2 bar, 4 1 foo, 1 4 qux]

albeit with an ugly mix of tabs and spaces. One final sort by <first_line> gives us

[4 1 foo, 1 2 bar, 1 4 qux]

and then it's just a matter of formatting the output:

[foo 4, bar 1, qux 1]

The generally-useful point is that the classic shell utilities really do work pretty well if you're operating within their paradigm, which isn't "throw everything in a hash table". (That's the paradigm of later scripting languages.)

the point is to do a stable sort on (word, line number) lexicographically, then when we do "uniq" we can take the first line number.

In contrast to the "we need a frequency table" idea in the article, this solution trades off memory by transferring all the line numbers in the stream. This is very much in the spirit of the infamous McIlroy/Knuth "bakeoff"[1] -- tradeoff some efficiency (via extra book-keeping or sorts) in return for composability.

Agreed, very neat.

[1] https://homepages.cwi.nl/~storm/teaching/reader/BentleyEtAl8...