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 heritage of the American Revolution is forgotten, and the American government, for better and for worse, has entered into the heritage of Europe as though it were its patrimony—unaware, alas, of the fact that Europe’s declining power was preceded and accompanied by political bankruptcy, the bankruptcy of the nation-state and its concept of sovereignty.”
—Hannah Arendt (1906–1975)
“Our flag is red, white and blue, but our nation is a rainbow—red, yellow, brown, black and white—and we’re all precious in God’s sight.”
—Jesse Jackson (b. 1941)
“Alice felt dreadfully puzzled. The Hatter’s remark seemed to her to have no sort of meaning in it, and yet it was certainly English. “I don’t quite understand you,” she said, as politely as she could.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)