# Sorting and Related Functions¶

Julia has an extensive, flexible API for sorting and interacting with already-sorted arrays of values. By default, Julia picks reasonable algorithms and sorts in standard ascending order:

`julia>sort([2,3,1])3-elementArray{Int64,1}:123`

You can easily sort in reverse order as well:

`julia>sort([2,3,1],rev=true)3-elementArray{Int64,1}:321`

To sort an array in-place, use the “bang” version of the sort function:

`julia>a=[2,3,1];julia>sort!(a);julia>a3-elementArray{Int64,1}:123`

Instead of directly sorting an array, you can compute a permutation of the array’s indices that puts the array into sorted order:

`julia>v=randn(5)5-elementArray{Float64,1}:0.2972880.382396-0.597634-0.0104452-0.839027julia>p=sortperm(v)5-elementArray{Int64,1}:53412julia>v[p]5-elementArray{Float64,1}:-0.839027-0.597634-0.01044520.2972880.382396`

Arrays can easily be sorted according to an arbitrary transformation of their values:

`julia>sort(v,by=abs)5-elementArray{Float64,1}:-0.01044520.2972880.382396-0.597634-0.839027`

Or in reverse order by a transformation:

`julia>sort(v,by=abs,rev=true)5-elementArray{Float64,1}:-0.839027-0.5976340.3823960.297288-0.0104452`

If needed, the sorting algorithm can be chosen:

`julia>sort(v,alg=InsertionSort)5-elementArray{Float64,1}:-0.839027-0.597634-0.01044520.2972880.382396`

All the sorting and order related functions rely on a “less than”
relation defining a total order on the values to be manipulated. The
`isless`

function is invoked by default, but the relation can be
specified via the `lt`

keyword.

## Sorting Functions¶

`sort!`

(*v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Sort the vector

`v`

in place.`QuickSort`

is used by default for numeric arrays while`MergeSort`

is used for other arrays. You can specify an algorithm to use via the`alg`

keyword (see Sorting Algorithms for available algorithms). The`by`

keyword lets you provide a function that will be applied to each element before comparison; the`lt`

keyword allows providing a custom “less than” function; use`rev=true`

to reverse the sorting order. These options are independent and can be used together in all possible combinations: if both`by`

and`lt`

are specified, the`lt`

function is applied to the result of the`by`

function;`rev=true`

reverses whatever ordering specified via the`by`

and`lt`

keywords.

`sort`

(*v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Variant of

`sort!`

that returns a sorted copy of`v`

leaving`v`

itself unmodified.

`sort`

(*A, dim, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false]*)Sort a multidimensional array

`A`

along the given dimension.

`sortperm`

(*v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Return a permutation vector of indices of

`v`

that puts it in sorted order. Specify`alg`

to choose a particular sorting algorithm (see Sorting Algorithms).`MergeSort`

is used by default, and since it is stable, the resulting permutation will be the lexicographically first one that puts the input array into sorted order – i.e. indices of equal elements appear in ascending order. If you choose a non-stable sorting algorithm such as`QuickSort`

, a different permutation that puts the array into order may be returned. The order is specified using the same keywords as`sort!`

.See also

`sortperm!()`

`sortperm!`

(*ix, v, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false,] [initialized=false]*)¶Like

`sortperm`

, but accepts a preallocated index vector`ix`

. If`initialized`

is`false`

(the default), ix is initialized to contain the values`1:length(v)`

.See also

`sortperm()`

`sortrows`

(*A, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Sort the rows of matrix

`A`

lexicographically.

`sortcols`

(*A, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Sort the columns of matrix

`A`

lexicographically.

## Order-Related Functions¶

`issorted`

(*v, [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Test whether a vector is in sorted order. The

`by`

,`lt`

and`rev`

keywords modify what order is considered to be sorted just as they do for`sort`

.

`searchsorted`

(*a, x, [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Returns the range of indices of

`a`

which compare as equal to`x`

according to the order specified by the`by`

,`lt`

and`rev`

keywords, assuming that`a`

is already sorted in that order. Returns an empty range located at the insertion point if`a`

does not contain values equal to`x`

.

`searchsortedfirst`

(*a, x, [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Returns the index of the first value in

`a`

greater than or equal to`x`

, according to the specified order. Returns`length(a)+1`

if`x`

is greater than all values in`a`

.

`searchsortedlast`

(*a, x, [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Returns the index of the last value in

`a`

less than or equal to`x`

, according to the specified order. Returns`0`

if`x`

is less than all values in`a`

.

`select!`

(*v, k, [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Partially sort the vector

`v`

in place, according to the order specified by`by`

,`lt`

and`rev`

so that the value at index`k`

(or range of adjacent values if`k`

is a range) occurs at the position where it would appear if the array were fully sorted via a non-stable algorithm. If`k`

is a single index, that value is returned; if`k`

is a range, an array of values at those indices is returned. Note that`select!`

does not fully sort the input array.

`select`

(*v, k, [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Variant of

`select!`

which copies`v`

before partially sorting it, thereby returning the same thing as`select!`

but leaving`v`

unmodified.

`selectperm`

(*v, k, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false]*)¶Return a partial permutation of the vector

`v`

, according to the order specified by`by`

,`lt`

and`rev`

, so that`v[output]`

returns the first`k`

(or range of adjacent values if`k`

is a range) values of a fully sorted version of`v`

. If`k`

is a single index (Integer), an array of the first`k`

indices is returned; if`k`

is a range, an array of those indices is returned. Note that the handling of integer values for`k`

is different from`select`

in that it returns a vector of`k`

elements instead of just the`k`

th element. Also note that this is equivalent to, but more efficient than, calling`sortperm(...)[k]`

`selectperm!`

(*ix, v, k, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false,] [initialized=false]*)¶Like

`selectperm`

, but accepts a preallocated index vector`ix`

. If`initialized`

is`false`

(the default), ix is initialized to contain the values`1:length(ix)`

.

## Sorting Algorithms¶

There are currently four sorting algorithms available in base Julia:

`InsertionSort`

`QuickSort`

`PartialQuickSort(k)`

`MergeSort`

`InsertionSort`

is an O(n^2) stable sorting algorithm. It is efficient
for very small `n`

, and is used internally by `QuickSort`

.

`QuickSort`

is an O(n log n) sorting algorithm which is in-place,
very fast, but not stable – i.e. elements which are considered
equal will not remain in the same order in which they originally
appeared in the array to be sorted. `QuickSort`

is the default
algorithm for numeric values, including integers and floats.

`PartialQuickSort(k)`

is similar to `QuickSort`

, but the output array
is only sorted up to index `k`

if `k`

is an integer, or in the range
of `k`

if `k`

is an `OrdinalRange`

. For example:

`x=rand(1:500,100)k=50k2=50:100s=sort(x;alg=QuickSort)ps=sort(x;alg=PartialQuickSort(k))qs=sort(x;alg=PartialQuickSort(k2))map(issorted,(s,ps,qs))# => (true, false, false)map(x->issorted(x[1:k]),(s,ps,qs))# => (true, true, false)map(x->issorted(x[k2]),(s,ps,qs))# => (true, false, true)s[1:k]==ps[1:k]# => trues[k2]==qs[k2]# => true`

`MergeSort`

is an O(n log n) stable sorting algorithm but is not
in-place – it requires a temporary array of half the size of the
input array – and is typically not quite as fast as `QuickSort`

.
It is the default algorithm for non-numeric data.

The default sorting algorithms are chosen on the basis that they are
fast and stable, or *appear* to be so. For numeric types indeed,
`QuickSort`

is selected as it is faster and indistinguishable in
this case from a stable sort (unless the array records its mutations
in some way). The stability property comes at a non-negligible cost,
so if you don’t need it, you may want to explicitly specify your
preferred algorithm, e.g. `sort!(v,alg=QuickSort)`

.

The mechanism by which Julia picks default sorting algorithms is
implemented via the `Base.Sort.defalg`

function. It allows a
particular algorithm to be registered as the default in all sorting
functions for specific arrays. For example, here are the two default
methods from sort.jl:

`defalg(v::AbstractArray)=MergeSortdefalg{T<:Number}(v::AbstractArray{T})=QuickSort`

As for numeric arrays, choosing a non-stable default algorithm for array types for which the notion of a stable sort is meaningless (i.e. when two values comparing equal can not be distinguished) may make sense.