Sorting Algorithms

The SortingAlgorithms package provides three sorting algorithms that can be used with Julia's standard sorting API:

• HeapSort – an unstable, general purpose, in-place, O(n log n) comparison sort that works by heapifying an array and repeatedly taking the maximal element from the heap.
• TimSort – a stable, general purpose, hybrid, O(n log n) comparison sort that adapts to different common patterns of partially ordered input data.
• RadixSort – a stable, special case, O(n) non-comparison sort that works by sorting data with fixed size, one digit at a time.

Usage

	julia> using SortingAlgorithms

	julia> words = map(chomp,[readlines(open("/usr/share/dict/words"))...])
	235886-element Array{ASCIIString,1}:
	 "A"
	 "a"
	 "aa"
	 "aal"
	 "aalii"
	 ⋮
	 "zythem"
	 "Zythia"
	 "zythum"
	 "Zyzomys"
	 "Zyzzogeton"

	julia> sort!(words, alg=TimSort)
	235886-element Array{ASCIIString,1}:
	 "A"
	 "Aani"
	 "Aaron"
	 "Aaronic"
	 "Aaronical"
	 ⋮
	 "zymotize"
	 "zymotoxic"
	 "zymurgy"
	 "zythem"
	 "zythum"

	julia> sort!(words, alg=TimSort, by=length)
	235886-element Array{ASCIIString,1}:
	 "A"
	 "B"
	 "C"
	 "D"
	 "E"
	 ⋮
	 "formaldehydesulphoxylate"
	 "pathologicopsychological"
	 "scientificophilosophical"
	 "tetraiodophenolphthalein"
	 "thyroparathyroidectomize"

	julia> sort!(words, alg=HeapSort)
	235886-element Array{ASCIIString,1}:
	 "A"
	 "Aani"
	 "Aaron"
	 "Aaronic"
	 "Aaronical"
	 ⋮
	 "zymotize"
	 "zymotoxic"
	 "zymurgy"
	 "zythem"
	 "zythum"

	julia> sort!(words, alg=HeapSort, by=length)
	235886-element Array{ASCIIString,1}:
	 "L"
	 "p"
	 "U"
	 "I"
	 "q"
	 ⋮
	 "pathologicopsychological"
	 "formaldehydesulphoxylate"
	 "scientificophilosophical"
	 "tetraiodophenolphthalein"
	 "thyroparathyroidectomize"

	julia> sort!(words, alg=RadixSort)
	ERROR: Radix sort only sorts bits types (got ASCIIString)
	 in error at error.jl:21
	 in sort! at /Users/stefan/.julia/SortingAlgorithms/src/SortingAlgorithms.jl:54
	 in sort! at sort.jl:328
	 in sort! at sort.jl:329

	julia> floats = randn(1000)
	1000-element Array{Float64,1}:
	  1.729
	  0.907196
	  0.461481
	 -0.204763
	 -0.16022
	  ⋮
	  0.700683
	 -0.236204
	 -2.15634
	 -0.316188
	 -0.171478

	julia> sort!(floats, alg=RadixSort)
	1000-element Array{Float64,1}:
	 -2.86255
	 -2.72041
	 -2.58234
	 -2.57259
	 -2.53046
	  ⋮
	  3.08307
	  3.12902
	  3.15075
	  3.20058
	  3.23942