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:
“In Africa I had indeed found a sufficiently frightful kind of loneliness but the isolation of this American ant heap was even more shattering.”
—Louis-Ferdinand Céline (1894–1961)
“My dream is that as the years go by and the world knows more and more of America, it ... will turn to America for those moral inspirations that lie at the basis of all freedom ... that America will come into the full light of the day when all shall know that she puts human rights above all other rights, and that her flag is the flag not only of America but of humanity.”
—Woodrow Wilson (1856–1924)
“His moving impulse is no flabby yearning to teach, to expound, to make simple; it is that “obscure inner necessity” of which Conrad tells us, the irresistible creative passion of a genuine artist, standing spell-bound before the impenetrable enigma that is life, enamoured by the strange beauty that plays over its sordidness, challenged to a wondering and half-terrified sort of representation of what passes understanding.”
—H.L. (Henry Lewis)