American flag sort


An American flag sort is an efficient, in-place variant of radix sort that distributes items into 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 American flag sort comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes".

Algorithm

Sorting algorithms in general sort a list of objects according to some ordering scheme. In contrast to comparison-based sorting algorithms, such as quicksort, American flag sort can only sort integers. In-place sorting algorithms, including American flag sort, run without allocating a significant amount of memory beyond that used by the original array. This is a significant advantage, both in memory savings and in time saved copying the array.
American flag sort works by successively dividing a list of objects into buckets based on the first digit of their base-N representation. When N is 2, each object can be swapped into the correct bucket by using the Dutch national flag algorithm. When N is larger, however, objects cannot be immediately swapped into place, because it is unknown where each bucket should begin and end. American flag sort gets around this problem by making two passes through the array. The first pass counts the number of objects that belong in each of the N buckets. The beginning and end of each bucket in the original array is then computed as the sum of sizes of preceding buckets. The second pass swaps each object into place.
American flag sort is most efficient with a radix that is a power of 2, because bit-shifting operations can be used instead of expensive exponentiations to compute the value of each digit. When sorting strings using 8- or 7-bit encodings such as ASCII, it is typical to use a radix of 256 or 128, which amounts to sorting character-by-character.

Performance considerations

It is worth noting that for pure English alphabet text, the counts histogram is always sparse. Depending on the hardware, it may be worth clearing the counts in correspondence with completing a bucket Or it may be worth maintaining a max and min active bucket, or a more complex data structure suitable for sparse arrays. It is also important to use a more basic sorting method for very small data sets, except in pathological cases where keys may share very long prefixes.
Most critically, this algorithm follows a random permutation, and is thus particularly cache-unfriendly for large datasets. It is a suitable algorithm in conjunction with a k-way merge algorithm.

Pseudocode


american_flag_sort
 for each digit D:
 # first pass: compute counts
 Counts <- zeros
 for object X in Array:
 Counts += 1
 # compute bucket offsets
 Offsets <- 
 # swap objects into place
 for object X in Array:
 swap X to the bucket starting at Offsets
 for each Bucket:
 american_flag_sort

Sample implementation in Python

This example written in the Python programming language will perform American flag sort for any radix of 2 or greater. Simplicity of exposition is chosen over clever programming, and so the log function is used instead of bit shifting techniques.

def get_radix_val -> int:
return int % radix
def compute_offsets:
counts =
for i in range:
val = get_radix_val
counts += 1
offsets =
sum = 0
for i in range:
offsets = sum
sum += counts
return offsets
def swap -> None:
i = start
next_free = copy
cur_block = 0
while cur_block < radix-1:
if i >= start + offsets:
cur_block += 1
continue
radix_val = get_radix_val
if radix_val cur_block:
i += 1
continue
swap_to = start + next_free
a_list, a_list = a_list, a_list
next_free += 1
def american_flag_sort_helper -> None:
offsets = compute_offsets
swap
if digit 0:
return
for i in range:
american_flag_sort_helper
def american_flag_sort -> None:
for x in a_list:
assert
max_val = max
max_digit = int
american_flag_sort_helper

General