Sorting and Related Functions¶

Julia has an extensive, flexible API for sorting and interacting with already-sorted arrays of values. For many users, sorting in standard ascending order, letting Julia pick reasonable default algorithms will be sufficient:

julia> sort([2,3,1])
3-element Array{Int64,1}:
 1
 2
 3

You can easily sort in reverse order as well:

julia> sort([2,3,1], rev=true)
3-element Array{Int64,1}:
 3
 2
 1

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

julia> a = [2,3,1];

julia> sort!(a);

julia> a
3-element Array{Int64,1}:
 1
 2
 3

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-element Array{Float64,1}:
  0.297288
  0.382396
 -0.597634
 -0.0104452
 -0.839027

julia> p = sortperm(v)
5-element Array{Int64,1}:
 5
 3
 4
 1
 2

julia> v[p]
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

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

julia> sort(v, by=abs)
5-element Array{Float64,1}:
 -0.0104452
  0.297288
  0.382396
 -0.597634
 -0.839027

Or in reverse order by a transformation:

julia> sort(v, by=abs, rev=true)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
  0.382396
  0.297288
 -0.0104452

Reasonable sorting algorithms are used by default, but you can choose other algorithms as well:

julia> sort(v, alg=InsertionSort)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

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

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.

Sorting Algorithms¶

There are currently three sorting algorithms available in base Julia:

InsertionSort
QuickSort
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.

MergeSort is an O(n log n) stable sorting algorithm but is not in-place – it requires a temporary array of equal size to the input array – and is typically not quite as fast as QuickSort. It is the default algorithm for non-numeric data.

The sort functions select a reasonable default algorithm, depending on the type of the array to be sorted. To force a specific algorithm to be used for sort or other soring functions, supply alg=<algorithm> as a keyword argument after the array to be sorted.

Sorting and Related Functions¶

Sorting Functions¶

Order-Related Functions¶

Sorting Algorithms¶