American flag sort works by in turn dividing a listing of objects into buckets supported the first digit of their base-N illustration (the base used is stated as the radix). once N is 2, every object can be swapped into the correct bucket by using the Dutch national flag algorithmic rule. once N is larger, however, objects can not be instantly swapped into place, because it is unknown where every bucket ought to begin and finish. American flag sort gets around this downside by making 2 passes through the array. the primary pass counts the objects that belong in every of the N buckets. the start and finish of every bucket within the original array is then computed because of the total of sizes of preceding buckets. The second pass swaps every object into place.

PsuedoCode:

american_flag_sort(Array, Radix)
  for each digit D:
    # first pass: compute counts
    Counts <- zeros(Radix)
    for object X in Array:
      Counts[digit D of object X in base Radix] += 1
    # compute bucket offsets
    Offsets <- [ sum(Counts[0..i]) for i in 1..Radix]
    # swap objects into place
    for object X in Array:
      swap X to the bucket starting at Offsets[digit D of X in base Radix]
    for each Bucket:
      american_flag_sort(Bucket, Radix)

Difference from Bucket Sort: (Quora)

  • Both Bucket sort and American Flag sort are mainly classified as ‘Distribution Sorting’ algorithms.
  • Distribution Sort- where items are distributed from the input to multiple intermediate structures, which are then gathered and placed on the output.
  • American Flag Sort is categorized as ‘ in-place’ , String sorting algorithms.
  • Bucket sort is not ‘in-place’ , stable algorithm. best for sorting integers.