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!.

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.