An american flag sort is an efficient, in-place variant of radix sort that distributes items into hundreds of buckets. Non-comparative sorting algorithms such as radix sort and american flag sort are typically used to sort large objects such as strings, for which comparison is not a unit-time operation.
American flag sort iterates through the bits of the objects, considering several bits of each object at a time. For each set of bits, american flag sort makes two passes through the array of objects: first to count the number of objects that will fall in each bin, and second to place each object in its bucket. This works especially well when sorting a byte at a time, using 256 buckets. With some optimizations, it is twice as fast as quicksort for large sets of strings.
The name comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes".
Read more about American Flag Sort: Algorithm, Sample Implementation in Python
Famous quotes containing the words american, flag and/or sort:
“The moment when she crawled out onto the back of the open limousine in which her husband had been murdered was the first and last time the American people would see Jacqueline Bouvier Kennedy Onassis crawl.... She was the last great private public figure in this country. In a time of gilt and glitz and perpetual revelation, she was perpetually associated with that thing so difficult to describe yet so simple to recognize, the apotheosis of dignity.”
—Anna Quindlen (b. 1952)
“—Here, the flag snaps in the glare and silence
Of the unbroken ice. I stand here,
The dogs bark, my beard is black, and I stare
At the North Pole. . .
And now what? Why, go back.
Turn as I please, my step is to the south.”
—Randall Jarrell (1914–1965)
“There is a sort of exotic preposterousness about a lot of elections, the way arguments are made even cruder.”
—Chris Patten (b. 1944)