tag

#american-flag-sort

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

American Flag Sort

American Flag Sort American flag sort is an in place variant of radix sort. It distributes elements into buckets based on a digit, then permutes them into correct positions using cycle leader permutation. Unlike standard radix sort, it avoids auxiliary arrays. This algorithm is commonly used for large datasets where memory allocation must be minimized. Problem Given an array $A$ of keys with digits in range $[0, b)$, reorder the...

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

American Flag String Sort

American Flag String Sort American flag string sort is an in-place MSD radix sort for strings. It partitions strings by the character at the current position, then recursively sorts each bucket by the next character. It uses the same bucket permutation idea as American flag sort, but the digit source is a string character rather than an integer digit. Problem Given an array $A$ of strings, sort the strings in...