American flag sort

The name American flag sort comes by analogy with the Dutch national flag problem[2] in the last step: efficiently partition the array into many "stripes".

[1] https://en.m.wikipedia.org/wiki/American_flag_sort

[2] https://en.m.wikipedia.org/wiki/Dutch_national_flag_problem

remram3• 2 years ago

Or in-place radix sort maybe.

I agree with you, the name is ridiculous, reminds me of miracle sort or intelligent design sort: https://www.dangermouse.net/esoteric/intelligentdesignsort.h...

Probably those two flag sort algorithms were named before the joke algorithms were popularily known.

thefifthsetpin• 2 years ago

Quicksort isn't great when comparing two items is expensive.

owlninja• 2 years ago

The 'more information' site linked on the page seems like something some HN folk love.

https://www.workmall.com/flags/united_states_flag.html

defrost• 2 years ago

There's a Peter M. McIlroy as well!?!

All this time and I thought it was just Doug, I'm guessing Peter might be the son of the father of pipe?

icsa• 2 years ago

Yes. He is a software engineer in Seattle.

jdeisenberg• 2 years ago

Wondering how this sort would perform with Unicode input (given 256 buckets); specifically what the results would look like.

bawolff2• 2 years ago

Presumably it would be fine, since unicode input is still a string of bytes at the end of the day.

nanidin3• 2 years ago

It says it sorts one byte at a time. I think this would break for anything not utf-8.

moonchild2• 2 years ago

Unicode collation is very complex. If you wanted to sort according to that, then you would need to devise an isomorphism between unicode strings and bitstrings such that lexicographic ordering in the bitstring domain agrees with unicode collation in the unicode domain. I'm not saying it's impossible, but it's not at all obvious how to do it. On the other hand, if all you want is some total order for acceleration structures, then you can indeed just use an arbitrary encoding like utf8 and do the obvious thing.

dhosek• 2 years ago

Ignoring the fact that if you have Unicode encoded strings, you probably want some sort of lexical sort rather than a sort on the raw Unicode character codes which is semantically meaningless, there is no reason to assume that Unicode data would be any different to sort than any other data.

seanhunter• 2 years ago

I think unicode is intrinsically antithetical to freedom. This would do great with ASCII.

re• 2 years ago

Looks like there's a Rust implementation: https://crates.io/crates/afsort

When sorting English words, this implementation seems to be about 40% faster than sort_unstable from the Rust standard library.

That's better than I would have expected. It would be interesting to see how it does on other types of string sort problems.

antonhag2• 2 years ago

Hi! Crate author here, happy to see my old project getting mentioned. Let me know if you have any questions!

ewalk153• 2 years ago

Do you actively use this function in any projects? What was your inspiration to write the crate?

Zelizz2• 2 years ago

Pretty much just a variation of counting sort with a worse name? https://en.wikipedia.org/wiki/Counting_sort

carabiner• 2 years ago

A superior name.

dumbo-octopus3• 2 years ago

No. The very article you link details the difference, and that Counting Sort is often a subroutine in Radix Sort, and that Counting Sort is extremely poorly suited to strings, which is the entire purpose of this sort. And this name is better. So... "no" in basically every way possible.

Zelizz2• 2 years ago

Characters in a string can be thought of as digits in a base-256 number. Call counting sort recursively on each bucket, looking at the next character in the string. Can you not see the similarity?

sltkr• 2 years ago

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

Someone• 2 years ago

The paper (https://static.usenix.org/publications/compsystems/1993/win_...; linked to from the page) is well-written and worth reading, iterating over multiple C programs that build up to this sort algorithm and giving a good rationale for each iteration.

awanderingmind• 2 years ago

There is currently a typo in the link which prevents it from working - the correct link is https://static.usenix.org/publications/compsystems/1993/win_...

Interesting read, thanks!

Traubenfuchs• 2 years ago

it is twice as fast as quicksort for large sets of string

Define large.

TheRealPomax• 2 years ago

They did. But you'll need to read the (free) paper [1] to get the details omitted in the NITS catalog summary.

[1] http://www.usenix.org/publications/compsystems/1993/win_mcil...

Oarch• 2 years ago

The comments made me realise there's no national flag with lots of vertical stripes. Seems like a hole in the market.

Someone alert CGP Grey!

Kon-Peki• 2 years ago

Sorts like these work really well on GPUs. You would start with a single thread for the first pass and then keep spawning one-thread-per-bucket for every additional pass until done. It isn't particularly taxing on the GPU; your advantage comes from being able to run potentially thousands of threads simultaneously without having to worry about coordinating read/write memory access.

NikkiA• 2 years ago

This strikes me that it should parallelize pretty well if you deputise the individual stripes to multiple threads.

franze• 2 years ago

today i coded franzSort, faster than mergeSort, slower than quickSort

function franzSort(a) { function m(l, r) { let s = []; while (l.length && r.length) { if (l[0] <= r[0]) { s.push(l.shift()); } else { s.push(r.shift()); } } return s.concat(l).concat(r); }

    if (a.length <= 1) {
        return a;
    }
    let h = Math.floor(a.length / 2);
    return m(franzSort(a.slice(0, h)), franzSort(a.slice(h)));

}

// Example usage let arr = [5, 3, 8, 6, 2, 7, 1, 4]; let sortedArr = franzSort(arr); console.log(sortedArr);

jon_richards• 2 years ago

The stars in the American flag aren't used. This is clearly Pride flag sort.

oniony• 2 years ago

And Mauritius's flag has more stripes.

American flag sort

Related Stories