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 ascending order:

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

You can sort in reverse order as well:

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

sort constructs a sorted copy leaving its input unchanged. Use the "bang" version of the sort function to mutate an existing array:

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

julia> sort!(a);

julia> a
3-element Vector{Int64}:
 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 be sorted according 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

If needed, the sorting algorithm can be chosen:

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

All the sorting and order related functions rely on a "less than" relation defining a strict weak order on the values to be manipulated. The isless function is invoked by default, but the relation can be specified via the lt keyword, a function that takes two array elements and returns true if and only if the first argument is "less than" the second. See sort! and Alternate Orderings for more information.

Sorting Functions

Base.sort! — Function

sort!(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sort the vector v in place. A stable algorithm is used by default: the ordering of elements that compare equal is preserved. A specific algorithm can be selected via the alg keyword (see Sorting Algorithms for available algorithms).

Elements are first transformed with the function by and then compared according to either the function lt or the ordering order. Finally, the resulting order is reversed if rev=true (this preserves forward stability: elements that compare equal are not reversed). The current implemention applies the by transformation before each comparison rather than once per element.

Passing an lt other than isless along with an order other than Base.Order.Forward or Base.Order.Reverse is not permitted, otherwise all options are independent and can be used together in all possible combinations. Note that order can also include a "by" transformation, in which case it is applied after that defined with the by keyword. For more information on order values see the documentation on Alternate Orderings.

Relations between two elements are defined as follows (with "less" and "greater" exchanged when rev=true):

x is less than y if lt(by(x), by(y)) (or Base.Order.lt(order, by(x), by(y))) yields true.
x is greater than y if y is less than x.
x and y are equivalent if neither is less than the other ("incomparable" is sometimes used as a synonym for "equivalent").

The result of sort! is sorted in the sense that every element is greater than or equivalent to the previous one.

The lt function must define a strict weak order, that is, it must be

irreflexive: lt(x, x) always yields false,
asymmetric: if lt(x, y) yields true then lt(y, x) yields false,
transitive: lt(x, y) && lt(y, z) implies lt(x, z),
transitive in equivalence: !lt(x, y) && !lt(y, x) and !lt(y, z) && !lt(z, y) together imply !lt(x, z) && !lt(z, x). In words: if x and y are equivalent and y and z are equivalent then x and z must be equivalent.

For example < is a valid lt function for Int values but ≤ is not: it violates irreflexivity. For Float64 values even < is invalid as it violates the fourth condition: 1.0 and NaN are equivalent and so are NaN and 2.0 but 1.0 and 2.0 are not equivalent.

Examples

julia> v = [3, 1, 2]; sort!(v); v
3-element Vector{Int64}:
 1
 2
 3

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

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v
3-element Vector{Tuple{Int64, String}}:
 (1, "c")
 (2, "b")
 (3, "a")

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
3-element Vector{Tuple{Int64, String}}:
 (3, "a")
 (2, "b")
 (1, "c")

julia> sort(0:3, by=x->x-2, order=Base.Order.By(abs)) # same as sort(0:3, by=abs(x->x-2))
4-element Vector{Int64}:
 2
 1
 3
 0

julia> sort([2, NaN, 1, NaN, 3]) # correct sort with default lt=isless
5-element Vector{Float64}:
   1.0
   2.0
   3.0
 NaN
 NaN

julia> sort([2, NaN, 1, NaN, 3], lt=<) # wrong sort due to invalid lt. This behavior is undefined.
5-element Vector{Float64}:
   2.0
 NaN
   1.0
 NaN
   3.0

Sorting Functions

Order-Related Functions

Sorting Algorithms

Alternate Orderings