# Talk:American flag sort

WikiProject United States (Rated Start-class, Low-importance)
This article is within the scope of WikiProject United States, a collaborative effort to improve the coverage of topics relating to the United States of America on Wikipedia. If you would like to participate, please visit the project page, where you can join the ongoing discussions.
Start  This article has been rated as Start-Class on the project's quality scale.
Low  This article has been rated as Low-importance on the project's importance scale.
WikiProject Computer science (Rated Start-class)
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start  This article has been rated as Start-Class on the project's quality scale.
WikiProject Computing (Rated Start-class)
This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start  This article has been rated as Start-Class on the project's quality scale.

## The sample Python code does not properly sort the array

There is something wrong with the implementation or it is partial and needs to be changed.

```from math import floor, log
from copy import copy

def compute_offsets(a_list, start, end, digit, radix):
counts = [0 for _ in range(radix)]
for i in range(start, end):
counts[val] += 1
offsets = [0 for _ in range(radix)]
sum = 0
offsets[i] = sum
sum += counts[i]
return offsets

def swap(a_list, offsets, start, end, digit, radix):
i = start
next_free = copy(offsets)
cur_block = 0
if i >= start + offsets[cur_block+1]:
cur_block += 1
continue
i += 1
continue
a_list[i], a_list[swap_to] = a_list[swap_to], a_list[i]

def american_flag_sort_helper(a_list, start, end, digit, radix):
offsets = compute_offsets(a_list, start, end, digit, radix)
swap(a_list, offsets, start, end, digit, radix)
if digit == 0:
return
for i in range(len(offsets)-1):

for x in a_list:
assert(type(x) == int)
max_val = max(a_list)

A = [((20*(x**3))//1)+67500 for x in range(-15,16)]
print(A)
import random
random.shuffle(A)
print(A)
american_flag_sort(A, 4)
print(A)
```

The output is:

```[0, 12620, 23560, 32940, 40880, 47500, 52920, 57260, 60640, 63180, 65000, 66220, 66960, 67340, 67480, 67500, 67520, 67660, 68040, 68780, 70000, 71820, 74360, 77740, 82080, 87500, 94120, 102060, 111440, 122380, 135000]
[74360, 60640, 111440, 32940, 65000, 66220, 0, 70000, 67500, 135000, 94120, 102060, 82080, 23560, 122380, 66960, 67480, 67520, 67340, 47500, 12620, 87500, 63180, 68780, 40880, 57260, 71820, 67660, 52920, 77740, 68040]
[0, 32940, 66960, 52920, 23560, 40880, 57260, 74360, 60640, 12620, 65000, 47500, 63180, 67480, 67520, 67340, 66220, 70000, 67500, 68780, 68040, 71820, 67660, 77740, 94120, 87500, 82080, 111440, 102060, 122380, 135000]
```

The last array, which is result from the function, is not properly sorted. Different radixes give different results, but none of them are correct.

Tested using Python 3.4.3 on Linux x64.

80.220.91.165 (talk) 10:23, 24 November 2015 (UTC)