American flag sort
xlinux.nist.gov
xlinux.nist.gov
Interesting read, thanks!
> 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.
> Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.
It’s an in-place bucket sort which is interesting.
> 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
...or from the very article itself...
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.
Wikipedia page https://en.wikipedia.org/wiki/American_flag_sort
OT: I quite liked the follow up video Youtube suggested -
Sorting algorithms to relax/study to - https://www.youtube.com/watch?v=vr5dCRHAgb0
I'm almost embarrassed by how long I've watched it!
Here's a visualization of a much larger data set that illustrates what's actually happening with the buckets and the major steps.
A
B
% printf "%s" A B | xxd -b -c4
00000000: 11110000 10011101 10010000 10110100 ....
00000004: 11110000 10011101 10010000 10110101 ....
% printf "%s" A B | xxd -c1 -ps | sort | xxd -r -ps | xxd -b -c4
00000000: 10010000 10010000 10011101 10011101 ....
00000004: 10110100 10110101 11110000 11110000 ....
% printf "%s" A B | xxd -c1 -ps | sort | xxd -r -ps
????????
https://unicode.org/reports/tr10
tl;dr from its wikipedia page:
> The Unicode collation algorithm (UCA) is an algorithm defined in Unicode Technical Report #10, which is a customizable method to produce binary keys from strings representing text in any writing system and language that can be represented with Unicode. These keys can then be efficiently compared byte by byte in order to collate or sort them according to the rules of the language, with options for ignoring case, accents, etc
All this time and I thought it was just Doug, I'm guessing Peter might be the son of the father of pipe?
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);
But where the classic radix sort is bottom-up, the American flag sort is top-down. That really matters for data where the the most significant portions of the data is likely to be all you need to consider for the sorting. While a top-down sort will have similar performance to bottom-up in the worst case, in the best case it can skip a lot of passes, especially if the inputs are much longer than the longest common prefix.
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
Define large.
[1] http://www.usenix.org/publications/compsystems/1993/win_mcil...
Someone alert CGP Grey!