
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.




package require Tcl 8.5
proc splitByRadix {lst base power} {
    # create a list of empty lists to hold the split by digit
    set out [lrepeat [expr {$base*2}] {}]
    foreach item $lst {
	# pulls the selected digit
	set digit [expr {($item / $base ** $power) % $base + $base * ($item >= 0)}]
	# append the number to the list selected by the digit
	lset out $digit [list {*}[lindex $out $digit] $item]
    }
    return $out
}
 
# largest abs value element of a list
proc tcl::mathfunc::maxabs {lst} {
    set max [abs [lindex $lst 0]]
    for {set i 1} {$i < [llength $lst]} {incr i} {
	set v [abs [lindex $lst $i]]
	if {$max < $v} {set max $v}
    }
    return $max
}
 
proc radixSort {lst {base 10}} {
    # there are as many passes as there are digits in the longest number
    set passes [expr {int(log(maxabs($lst))/log($base) + 1)}]
    # For each pass...
    for {set pass 0} {$pass < $passes} {incr pass} {
	# Split by radix, then merge back into the list
	set lst [concat {*}[splitByRadix $lst $base $pass]]
    }
    return $lst
}