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:
“I believe that the miseries consequent on the manufacture and sale of intoxicating liquors are so great as imperiously to command the attention of all dedicated lives; and that while the abolition of American slavery was numerically first, the abolition of the liquor traffic is not morally second.”
—Elizabeth Stuart Phelps (1844–1911)
“What is Americanism? Every one has a different answer. Some people say it is never to submit to the dictation of a King. Others say Americanism is the pride of liberty and the defence of an insult to the flag with their gore. When some half-developed person tramples on that flag, we should be ready to pour out the blood of the nation, they say. But do we not sit in silence when that flag waves over living conditions which should be an insult to all patriotism?”
—Anna Howard Shaw (1847–1919)
“The innocence of those who grind the faces of the poor, but refrain from pinching the bottoms of their neighbour’s wives! The innocence of Ford, the innocence of Rockefeller! The nineteenth century was the Age of Innocence—that sort of innocence. With the result that we’re now almost ready to say that a man is seldom more innocently employed than when making love.”
—Aldous Huxley (1894–1963)