News for hackers. Stuff that matters.
Re:American Flag Sort by chowells on Wednesday April 24, 2024 @11:53AM (#40145892)
There is no one who fails to see the similarity, because they're both kinds of radix sorts. For instance, a counting sort is a degenerate form of radix sort that only does one pass.

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.

There are no comments on this comment yet.