Overview
American Flag Sort is a sorting method that orders values by a named comparison, distribution, merge, or parallel network rule. It is useful when its stability, memory use, parallelism, or data-movement pattern fits the workload.
ExtendedSource checked
American Flag Sort
American Flag Sort orders records with a named compare, partition, or distribution strategy.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Intermediate
- Family
- Sorting
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
ordering relationcomparison stepdata movementordering rulecomparisonrearrangement
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)
When to Use
- Use American Flag Sort when its stability, memory, parallelism, or movement pattern fits the data.
- Use it when the input shape is known enough to choose beyond a generic library sort.
When Not to Use
- Avoid when a simpler standard library sort already gives the needed stability and performance.
- Avoid when the method's memory or data-movement pattern conflicts with the storage medium.
What It Does
- Reorders items by key
- Compares, partitions, merges, or distributes records
- Returns a sorted sequence
Use Cases
- Preparing data for search
- Ranking records
- External or parallel ordering
Inputs
- Unordered collection
- Comparison or key function
Outputs
- Ordered collection
- Partitioned or partially ordered collection
Pseudocode
- 1.Split, compare, distribute, or merge items according to the method
- 2.Maintain the method's ordering invariant
- 3.Move records into progressively more ordered positions
- 4.Repeat until every item is ordered
- 5.Return the sorted collection
Canonical Example
- Input
- values = [4, 1, 3, 2]
- Output
- [1, 2, 3, 4]
- Explanation
- American Flag Sort applies its ordering rule until all values are in sorted order.
Implementation Notes
- Document whether equal keys preserve original order.
- Benchmark on realistic input shapes, not only random arrays.
Common Pitfalls
- Mixing stable and unstable variants can reorder equal keys unexpectedly.
- Ignoring cache or external-memory behavior can dominate theoretical complexity.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow elements moving through compare, swap, merge, or distribution steps.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Split, compare, distribute, or merge items according to the method
sortingNotes
American Flag Sort operates in O(n log n) time and O(n) space within the Sorting family. Often compared with Merge Sort and Quick Sort.
Sources (2)
What each reference supports for this entry.
Algorithms in C, Parts 1-4
BookSorting reference for in-place radix sorting, byte-wise buckets, and American-flag style permutation.
NIST DADS: American Flag Sort
EncyclopediaDictionary reference for American flag sort as an in-place radix-sort variant with bucket counting and permutation.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofRadix Sort
American flag sort is an in-place radix sort variant that counts buckets and permutes items into final bucket ranges.
Related Algorithms
Tags
Sorting