[sltkr]

American flag sort is essentially an in-place version of counting sort.

That's talking about the single-pass American flag sort. If you use American flag sort to sort strings, you do multiple passes: on the first pass, you sort all strings by their first character, then for each starting character, you sort the strings with that starting character (which are now in a contiguous subarray) by their second character, and so on.

@chowells calls it a “top-down radix sort” below, which is a great description. It also explains the strengths and weaknesses of the two algorithms: radix sort works great for small strings of fixed length (e.g. IPv4 addresses, which can be thought of as 4-byte sequences) while American flag sort works great for variable-length strings like actual textual strings, especially if they don't share common prefixes (e.g. dictionary words, usernames, etc.)

@hinkley pointed out that the recursive version is just a bucket sort, but in-place. Which is also true!

tl;dr:

Single-pass American flag sort = in-place counting sort

Recursive American flag sort = in-place bucket sort