Sort Target
Algorithm
Speed
Normal ~12s · 34 ms ×3
American flag sort(1993)
▶ Try this Source
O(nk) ✗ Stable ✓ In-place
🔧 How it works

An in-place MSD Radix sort that makes two passes per digit: the first counts elements per bucket to compute bucket boundaries, the second cyclically permutes elements into their correct buckets without any auxiliary array.

🎯 Key property

Achieves MSD radix sorting with O(1) extra space beyond the fixed-size counting table, the cyclic permutation replaces the auxiliary buffer that standard MSD Radix sort requires.

👁 Watch for
  • IndexRead the first pass reads each element's current digit to build the count table and compute bucket boundary positions
  • Swap (cyclic permutation) in the second pass, each out-of-place element is swapped directly into its correct bucket; the displaced element is immediately re-routed to its own destination, continuing the cycle until the chain closes
  • End of pass once all elements sit in their correct bucket for the current digit, the algorithm recurses into each bucket for the next digit position
🕰 History 🌳 Lineage ⚡ Optimization
UsesHybrid SwitchingBit Tricks & Bit Packing
Initial State
This is the array before sorting. Follow American flag sort step by step.
Main Array
15
0
51
1
64
2
89
3
53
4
46
5
329
6
3
7
79
8
61
9
309
10
23
11
95
12
63
13
27
14
74
15
70
16
317
17
302
18
10
19
85
20
94
21
7
22
52
23
26
24
20
25
12
26
305
27
311
28
77
29
325
30
73
31
28
32
2
33
35
34
13
35
44
36
21
37
39
38
321
39
69
40
8
41
308
42
56
43
315
44
99
45
72
46
40
47
312
48
84
49
59
50
82
51
19
52
303
53
306
54
87
55
41
56
14
57
80
58
310
59
301
60
81
61
100
62
76
63
48
64
62
65
18
66
29
67
83
68
25
69
17
70
33
71
24
72
22
73
322
74
96
75
88
76
1
77
318
78
45
79
324
80
4
81
97
82
37
83
304
84
57
85
60
86
9
87
328
88
307
89
65
90
34
91
93
92
300
93
71
94
58
95
90
96
36
97
92
98
32
99
314
100
38
101
91
102
326
103
16
104
327
105
319
106
5
107
11
108
54
109
313
110
47
111
68
112
86
113
30
114
42
115
55
116
50
117
320
118
78
119
31
120
67
121
98
122
316
123
323
124
49
125
66
126
6
127
43
128
75
129
Buckets
Waiting for the first digit pass…
0 / 1,061 ops ( 0.0%) 0.0%
• © 2026 guitarrapc. All rights reserved.
Sorting is
a spectacle.
Algorithms at work, in a daily vertical feed. Watch, play, challenge — and go deeper when you're ready.
Loading 0%
An unhandled error has occurred. Reload 🗙