
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.




 
templates radixsort&{base:}
  sink bucketize
    def value: $;
    $ ~/ $@radixsort.digit -> #
    when <=0 ?($value <0..>)> do
      ..|@radixsort.positives: $value;
    when <=0> do
      ..|@radixsort.negatives(last): $value;
    otherwise
      def bucket: $ mod $base -> \(<?($value<0..>)> $ + 1 ! <=0> $base ! <> $ !\);
      ..|@radixsort.buckets($bucket): $value;
      @radixsort.done: 0;
  end bucketize
  // Negatives get completed in wrong length-order, we need to collect by length and correct at the end
  @: { done: 1, digit: 1"1", positives: [], negatives: [[]], buckets: [1..$base -> []]};
  $... -> !bucketize
  $@.done -> #
  when <=1> do
    [$@.negatives(last..1:-1)... ..., $@.positives...] !
  otherwise
    def previous: $@.buckets;
    ..|@: {done: 1, digit: $@.digit * $base, buckets:[1..$base -> []]};
    ..|@.negatives: [];
    $previous... ... -> !bucketize
    $@.done -> #
end radixsort
 
[170, 45, 75, 91, 90, 92, 802, 24, 2, 66] -> radixsort&{base:10} -> !OUT::write
'
' -> !OUT::write
[-170, -45, -91, -90, -92, -802, -24, -2, -76] -> radixsort&{base:10} -> !OUT::write
'
' -> !OUT::write
[170, 45, 75, -91, -90, -92, -802, 24, 2, 66] -> radixsort&{base:10} -> !OUT::write
'
' -> !OUT::write
[170, 45, 75, -91, -90, -92, -802, 24, 2, 66] -> radixsort&{base:3} -> !OUT::write
 