user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Counting sort. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

Task

Implement the Counting sort.   This is a way of sorting integers when the minimum and maximum value are known.

Pseudocode

```
function countingSort(array, min, max):
    count: array of (max - min + 1) elements
    initialize count with 0
    for each number in array do
        count[number - min] := count[number - min] + 1
    done
    z := 0
    for i from min to max do
        while ( count[i - min] > 0 ) do
            array[z] := i
            z := z+1
            count[i - min] := count[i - min] - 1
        done
    done

```

The *min* and *max* can be computed apart, or be known *a priori*.

**Note**:   we know that, given an array of integers,   its maximum and minimum values can be always found;   but if we imagine the worst case for an array that can hold up to 32 bit integers,   we see that in order to hold the counts,   an array of up to **232** elements may be needed.   I.E.:   we need to hold a count value up to **232-1**,   which is a little over 4.2 Gbytes.   So the counting sort is more practical when the range is (very) limited,   and minimum and maximum values are known   *a priori*.     (However, as a counterexample,   the use of   *sparse arrays*   minimizes the impact of the memory usage,   as well as removing the need of having to know the minimum and maximum values   *a priori*.)
assistant
(formerly Perl 6)

**Works with**: rakudo version 2018.03

```
sub counting-sort (@ints) {
    my $off = @ints.min;
    (my @counts)[$_ - $off]++ for @ints;
    flat @counts.kv.map: { ($^k + $off) xx ($^v // 0) }
}

# Testing:
constant @age-range = 2 .. 102;
my @ages = @age-range.roll(50);
say @ages.&counting-sort;
say @ages.sort;

say @ages.&counting-sort.join eq @ages.sort.join ?? 'ok' !! 'not ok';

```

Output:

```
(5 5 5 7 9 17 19 19 20 21 25 27 28 30 32 34 38 40 41 45 48 49 50 51 53 54 55 56 59 62 65 66 67 69 70 73 74 81 83 85 87 91 91 93 94 96 99 99 100 101)
(5 5 5 7 9 17 19 19 20 21 25 27 28 30 32 34 38 40 41 45 48 49 50 51 53 54 55 56 59 62 65 66 67 69 70 73 74 81 83 85 87 91 91 93 94 96 99 99 100 101)
ok

```