
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort




Task

Sort an integer array with the   radix sort algorithm.

The primary purpose is to complete the characterization of sort algorithms task.




import std.stdio, std.math, std.traits, std.range, std.algorithm;
 
ElementType!R[] radixSort(size_t N=10, R)(R r)
if (hasLength!R && isRandomAccessRange!R &&
    isIntegral!(ElementType!R)) {
    alias ElementType!R E;
 
    static if (isDynamicArray!R)
        alias r res;         // input is array => in place sort
    else
        E[] res = r.array(); // input is Range => return a new array
 
    E absMax = r.map!abs().reduce!max();
    immutable nPasses = 1 + cast(int)(log(absMax) / log(N));
 
    foreach (pass; 0 .. nPasses) {
        auto bucket = new E[][](2 * N - 1, 0);
        foreach (v; res) {
            int bIdx = abs(v / (N ^^ pass)) % N;
            bIdx = (v < 0) ? -bIdx : bIdx;
            bucket[N + bIdx - 1] ~= v;
        }
        res = bucket.join();
    }
 
    return res;
}
 
void main() {
    auto items = [170, 45, 75, -90, 2, 24, -802, 66];
    items.radixSort().writeln();
    items.map!q{1 - a}().radixSort().writeln();
}