JuliaLang/julia — pull request #2066 by kmsquire (2013-01-17 06:00:01+00:00)
Title: WIP/RFC: Conversion/elimination of sort related functions (cf. #1850, #1539)

This patch was prompted by the discussion in #1850, though it goes a bit beyond that:

* Remove
* `insertionsort`,
* `quicksort`,
* `mergesort`,
* `timsort`

* in favor of

```julia
abstract SortingAlgorithm
type QuickSort <: SortingAlgorithm end
type InsertionSort <: SortingAlgorithm end
type MergeSort <: SortingAlgorithm end
type TimSort <: SortingAlgorithm end

function sort(InsertionSort,v)
...
end

function sort(QuickSort,v)
...
end

...
```

* Removed underscores from search related function names:
* `sort_by` -> `sortby`
* `issorted_{by,r}` -> `issorted{by,r}`
* `select_{by,r}` -> `select{by,r}`
* `search_sorted_*` -> `searchsorted*`

There is one general and a couple of specific issues I need feedback on:

1. What do people think of the `sort(SortName, v)` syntax? My opinion is that it's clearer to write and use, but I could go either way.

2. `@in_place_matrix_op` is a macro which creates versions of a function which operate along a dimension of a matrix. In this patch it is simplified to inline code generation. However, `shuffle` in `combinatorics.jl` also used this macro, and I'm not sure best how to proceed.

3. at @toivoh's suggestion in #1850, the function signature for specialized sorts is based on
```julia
function sort(::Type{MySort}, v::Vector)
```
However, since various forms of this function (`sort`, `sortby`, `sortr`, etc.) are produced using code generation, I had to jump through some hoops in order to properly prepend the type to the function arguments (see, e.g., https://github.com/kmsquire/julia/pull/new/sort-updates#L3R74). Is there a better way to do this?

There might be a very slight performance hit (up to a few percent), though the machine I tested this on was under load, so it's not clear.

Any other general comments/suggestions welcome.