JuliaLang/julia — pull request #3824 by kmsquire (2013-07-25 00:00:04+00:00)
Title: RFC: HeapSort

* Broke out `Ordering` from `Sort` so that it could be used by the heap routines before sort.jl was loaded
* Also minor updates/cleanup to `percolate_up`, `percolate_down`, `PriorityQueue`; if this doesn't go in, I'll break these out into a separate pull request.

I started this with the thought of turning `QuickSort` into `IntroSort` (i.e., if the recursion gets too deep, delegate to another sort method). The main benefit of `HeapSort` is that it's inplace. However, it's also slower, so for `IntroSort`, it might be better to delegate to `MergeSort` (and use more memory) by default.

```julia
test_type sort_alg log_size size *sort \sort /sort 3sort +sort ~sort =sort !sort
[1,] "Float64" "QuickSort" 20 1048576 0.131328 0.0427128 0.0453497 0.0460282 0.0671119 0.0651382 0.0543719 NA
[2,] "Float64" "QuickSort" 20 1048576 0.131547 0.04271 0.0456041 0.0458534 0.0671941 0.0633595 0.0544501 NA
[3,] "Float64" "QuickSort" 20 1048576 0.131705 0.0427248 0.0458225 0.045777 0.0673429 0.0636108 0.0546799 NA
[4,] "Float64" "MergeSort" 20 1048576 0.185617 0.113939 0.0713036 0.0729345 0.071276 0.118062 0.070506 0.0931192
[5,] "Float64" "MergeSort" 20 1048576 0.184979 0.113524 0.0705161 0.0761012 0.0707861 0.116829 0.0704944 0.0926133
[6,] "Float64" "MergeSort" 20 1048576 0.185654 0.114148 0.071414 0.0759432 0.0710218 0.116081 0.071349 0.0928292
[7,] "Float64" "HeapSort" 20 1048576 0.282344 0.117494 0.115659 0.115739 0.117018 0.106454 0.0234293 0.132989
[8,] "Float64" "HeapSort" 20 1048576 0.283148 0.119782 0.118256 0.117847 0.118228 0.104195 0.023398 0.131953
[9,] "Float64" "HeapSort" 20 1048576 0.281976 0.119261 0.118041 0.117146 0.117773 0.133388 0.0255029 0.148302
```

See https://github.com/kmsquire/SortPerf.jl for test descriptions.