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

Sort the vectorv 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 thealg keyword (seeSorting Algorithms for available algorithms).

Elements are first transformed with the functionby and then compared according to either the functionlt or the orderingorder. Finally, the resulting order is reversed ifrev=true (this preserves forward stability: elements that compare equal are not reversed). The current implementation applies theby transformation before each comparison rather than once per element.

Passing anlt other thanisless along with anorder other thanBase.Order.Forward orBase.Order.Reverse is not permitted, otherwise all options are independent and can be used together in all possible combinations. Note thatorder can also include a "by" transformation, in which case it is applied after that defined with theby keyword. For more information onorder values see the documentation onAlternate Orderings.

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

• x is less thany iflt(by(x), by(y)) (orBase.Order.lt(order, by(x), by(y))) yields true.
• x is greater thany ify is less thanx.
• x andy are equivalent if neither is less than the other ("incomparable" is sometimes used as a synonym for "equivalent").

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

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

• irreflexive:lt(x, x) always yieldsfalse,
• asymmetric: iflt(x, y) yieldstrue thenlt(y, x) yieldsfalse,
• transitive:lt(x, y) && lt(y, z) implieslt(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: ifx andy are equivalent andy andz are equivalent thenx andz must be equivalent.

For example< is a validlt function forInt values but≤ is not: it violates irreflexivity. ForFloat64 values even< is invalid as it violates the fourth condition:1.0 andNaN are equivalent and so areNaN and2.0 but1.0 and2.0 are not equivalent.

See alsosort,sortperm,sortslices,partialsort!,partialsortperm,issorted,searchsorted,insorted,Base.Order.ord.

Examples

julia> v = [3, 1, 2]; sort!(v); v3-element Vector{Int64}: 1 2 3julia> v = [3, 1, 2]; sort!(v, rev = true); v3-element Vector{Int64}: 3 2 1julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v3-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]); v3-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 0julia> sort([2, NaN, 1, NaN, 3]) # correct sort with default lt=isless5-element Vector{Float64}:   1.0   2.0   3.0 NaN NaNjulia> 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

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

Sort the multidimensional arrayA along dimensiondims. See the one-dimensional version ofsort! for a description of possible keyword arguments.

To sort slices of an array, refer tosortslices.

Examples

julia> A = [4 3; 1 2]2×2 Matrix{Int64}: 4  3 1  2julia> sort!(A, dims = 1); A2×2 Matrix{Int64}: 1  2 4  3julia> sort!(A, dims = 2); A2×2 Matrix{Int64}: 1  2 3  4

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

Variant ofsort! that returns a sorted copy ofv leavingv itself unmodified.

Examples

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

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

Sort a multidimensional arrayA along the given dimension. Seesort! for a description of possible keyword arguments.

To sort slices of an array, refer tosortslices.

Examples

julia> A = [4 3; 1 2]2×2 Matrix{Int64}: 4  3 1  2julia> sort(A, dims = 1)2×2 Matrix{Int64}: 1  2 4  3julia> sort(A, dims = 2)2×2 Matrix{Int64}: 3  4 1  2

sortperm(A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

Return a permutation vector or arrayI that putsA[I] in sorted order along the given dimension. IfA has more than one dimension, then thedims keyword argument must be specified. The order is specified using the same keywords assort!. The permutation is guaranteed to be stable even if the sorting algorithm is unstable: the indices of equal elements will appear in ascending order.

See alsosortperm!,partialsortperm,invperm,indexin. To sort slices of an array, refer tosortslices.

Examples

julia> v = [3, 1, 2];julia> p = sortperm(v)3-element Vector{Int64}: 2 3 1julia> v[p]3-element Vector{Int64}: 1 2 3julia> A = [8 7; 5 6]2×2 Matrix{Int64}: 8  7 5  6julia> sortperm(A, dims = 1)2×2 Matrix{Int64}: 2  4 1  3julia> sortperm(A, dims = 2)2×2 Matrix{Int64}: 3  1 2  4

InsertionSort

Use the insertion sort algorithm.

Insertion sort traverses the collection one element at a time, inserting each element into its correct, sorted position in the output vector.

Characteristics:

• stable: preserves the ordering of elements that compare equal

(e.g. "a" and "A" in a sort of letters that ignores case).

• in-place in memory.
• quadratic performance in the number of elements to be sorted:

it is well-suited to small collections but should not be used for large ones.

MergeSort

Indicate that a sorting function should use the merge sort algorithm. Merge sort divides the collection into subcollections and repeatedly merges them, sorting each subcollection at each step, until the entire collection has been recombined in sorted form.

Characteristics:

• stable: preserves the ordering of elements that compare equal (e.g. "a" and "A" in a sort of letters that ignores case).
• not in-place in memory.
• divide-and-conquer sort strategy.
• good performance for large collections but typically not quite as fast asQuickSort.

QuickSort

Indicate that a sorting function should use the quick sort algorithm, which isnot stable.

Characteristics:

• not stable: does not preserve the ordering of elements that compare equal (e.g. "a" and "A" in a sort of letters that ignores case).
• in-place in memory.
• divide-and-conquer: sort strategy similar toMergeSort.
• good performance for large collections.

PartialQuickSort{T <: Union{Integer,OrdinalRange}}

Indicate that a sorting function should use the partial quick sort algorithm.PartialQuickSort(k) is likeQuickSort, but is only required to find and sort the elements that would end up inv[k] werev fully sorted.

Characteristics:

• not stable: does not preserve the ordering of elements that compare equal (e.g. "a" and "A" in a sort of letters that ignores case).
• in-place in memory.
• divide-and-conquer: sort strategy similar toMergeSort.

Note thatPartialQuickSort(k) does not necessarily sort the whole array. For example,

julia> x = rand(100);julia> k = 50:100;julia> s1 = sort(x; alg=QuickSort);julia> s2 = sort(x; alg=PartialQuickSort(k));julia> map(issorted, (s1, s2))(true, false)julia> map(x->issorted(x[k]), (s1, s2))(true, true)julia> s1[k] == s2[k]true

sortperm!(ix, A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

Likesortperm, but accepts a preallocated index vector or arrayix with the sameaxes asA.ix is initialized to contain the valuesLinearIndices(A).

Examples

julia> v = [3, 1, 2]; p = zeros(Int, 3);julia> sortperm!(p, v); p3-element Vector{Int64}: 2 3 1julia> v[p]3-element Vector{Int64}: 1 2 3julia> A = [8 7; 5 6]; p = zeros(Int,2, 2);julia> sortperm!(p, A; dims=1); p2×2 Matrix{Int64}: 2  4 1  3julia> sortperm!(p, A; dims=2); p2×2 Matrix{Int64}: 3  1 2  4

sortslices(A; dims, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sort slices of an arrayA. The required keyword argumentdims must be either an integer or a tuple of integers. It specifies the dimension(s) over which the slices are sorted.

E.g., ifA is a matrix,dims=1 will sort rows,dims=2 will sort columns. Note that the default comparison function on one dimensional slices sorts lexicographically.

For the remaining keyword arguments, see the documentation ofsort!.

Examples

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1) # Sort rows3×3 Matrix{Int64}: -1   6  4  7   3  5  9  -2  8julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, lt=(x,y)->isless(x[2],y[2]))3×3 Matrix{Int64}:  9  -2  8  7   3  5 -1   6  4julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, rev=true)3×3 Matrix{Int64}:  9  -2  8  7   3  5 -1   6  4julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2) # Sort columns3×3 Matrix{Int64}:  3   5  7 -1  -4  6 -2   8  9julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, alg=InsertionSort, lt=(x,y)->isless(x[2],y[2]))3×3 Matrix{Int64}:  5   3  7 -4  -1  6  8  -2  9julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, rev=true)3×3 Matrix{Int64}: 7   5   3 6  -4  -1 9   8  -2

Higher dimensions

sortslices extends naturally to higher dimensions. E.g., ifA is a a 2x2x2 array,sortslices(A, dims=3) will sort slices within the 3rd dimension, passing the 2x2 slicesA[:, :, 1] andA[:, :, 2] to the comparison function. Note that while there is no default order on higher-dimensional slices, you may use theby orlt keyword argument to specify such an order.

Ifdims is a tuple, the order of the dimensions indims is relevant and specifies the linear order of the slices. E.g., ifA is three dimensional anddims is(1, 2), the orderings of the first two dimensions are re-arranged such that the slices (of the remaining third dimension) are sorted. Ifdims is(2, 1) instead, the same slices will be taken, but the result order will be row-major instead.

Higher dimensional examples

julia> A = [4 3; 2 1 ;;; 'A' 'B'; 'C' 'D']2×2×2 Array{Any, 3}:[:, :, 1] = 4  3 2  1[:, :, 2] = 'A'  'B' 'C'  'D'julia> sortslices(A, dims=(1,2))2×2×2 Array{Any, 3}:[:, :, 1] = 1  3 2  4[:, :, 2] = 'D'  'B' 'C'  'A'julia> sortslices(A, dims=(2,1))2×2×2 Array{Any, 3}:[:, :, 1] = 1  2 3  4[:, :, 2] = 'D'  'C' 'B'  'A'julia> sortslices(reshape([5; 4; 3; 2; 1], (1,1,5)), dims=3, by=x->x[1,1])1×1×5 Array{Int64, 3}:[:, :, 1] = 1[:, :, 2] = 2[:, :, 3] = 3[:, :, 4] = 4[:, :, 5] = 5

issorted(v, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Test whether a collection is in sorted order. The keywords modify what order is considered sorted, as described in thesort! documentation.

Examples

julia> issorted([1, 2, 3])truejulia> issorted([(1, "b"), (2, "a")], by = x -> x[1])truejulia> issorted([(1, "b"), (2, "a")], by = x -> x[2])falsejulia> issorted([(1, "b"), (2, "a")], by = x -> x[2], rev=true)truejulia> issorted([1, 2, -2, 3], by=abs)true

searchsorted(v, x; by=identity, lt=isless, rev=false)

Return the range of indices inv where values are equivalent tox, or an empty range located at the insertion point ifv does not contain values equivalent tox. The vectorv must be sorted according to the order defined by the keywords. Refer tosort! for the meaning of the keywords and the definition of equivalence. Note that theby function is applied to the searched valuex as well as the values inv.

The range is generally found using binary search, but there are optimized implementations for some inputs.

See also:searchsortedfirst,sort!,insorted,findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match3:3julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches4:5julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle3:2julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end7:6julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start1:0julia> searchsorted([1=>"one", 2=>"two", 2=>"two", 4=>"four"], 2=>"two", by=first) # compare the keys of the pairs2:3

searchsortedfirst(v, x; by=identity, lt=isless, rev=false)

Return the index of the first value inv that is not ordered beforex. If all values inv are ordered beforex, returnlastindex(v) + 1.

The vectorv must be sorted according to the order defined by the keywords.insert!ingx at the returned index will maintain the sorted order. Refer tosort! for the meaning and use of the keywords. Note that theby function is applied to the searched valuex as well as the values inv.

The index is generally found using binary search, but there are optimized implementations for some inputs.

See also:searchsortedlast,searchsorted,findfirst.

Examples

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # single match3julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # multiple matches4julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle3julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9) # no match, insert at end7julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no match, insert at start1julia> searchsortedfirst([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs3

searchsortedlast(v, x; by=identity, lt=isless, rev=false)

Return the index of the last value inv that is not ordered afterx. If all values inv are ordered afterx, returnfirstindex(v) - 1.

The vectorv must be sorted according to the order defined by the keywords.insert!ingx immediately after the returned index will maintain the sorted order. Refer tosort! for the meaning and use of the keywords. Note that theby function is applied to the searched valuex as well as the values inv.

The index is generally found using binary search, but there are optimized implementations for some inputs

Examples

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # single match3julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # multiple matches5julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle2julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # no match, insert at end6julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # no match, insert at start0julia> searchsortedlast([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs2

insorted(x, v; by=identity, lt=isless, rev=false) -> Bool

Determine whether a vectorv contains any value equivalent tox. The vectorv must be sorted according to the order defined by the keywords. Refer tosort! for the meaning of the keywords and the definition of equivalence. Note that theby function is applied to the searched valuex as well as the values inv.

The check is generally done using binary search, but there are optimized implementations for some inputs.

See alsoin.

Examples

julia> insorted(4, [1, 2, 4, 5, 5, 7]) # single matchtruejulia> insorted(5, [1, 2, 4, 5, 5, 7]) # multiple matchestruejulia> insorted(3, [1, 2, 4, 5, 5, 7]) # no matchfalsejulia> insorted(9, [1, 2, 4, 5, 5, 7]) # no matchfalsejulia> insorted(0, [1, 2, 4, 5, 5, 7]) # no matchfalsejulia> insorted(2=>"TWO", [1=>"one", 2=>"two", 4=>"four"], by=first) # compare the keys of the pairstrue

partialsort!(v, k; by=identity, lt=isless, rev=false)

Partially sort the vectorv in place so that the value at indexk (or range of adjacent values ifk is a range) occurs at the position where it would appear if the array were fully sorted. Ifk is a single index, that value is returned; ifk is a range, an array of values at those indices is returned. Note thatpartialsort! may not fully sort the input array.

For the keyword arguments, see the documentation ofsort!.

Examples

julia> a = [1, 2, 4, 3, 4]5-element Vector{Int64}: 1 2 4 3 4julia> partialsort!(a, 4)4julia> a5-element Vector{Int64}: 1 2 3 4 4julia> a = [1, 2, 4, 3, 4]5-element Vector{Int64}: 1 2 4 3 4julia> partialsort!(a, 4, rev=true)2julia> a5-element Vector{Int64}: 4 4 3 2 1

partialsort(v, k, by=identity, lt=isless, rev=false)

Variant ofpartialsort! that copiesv before partially sorting it, thereby returning the same thing aspartialsort! but leavingv unmodified.

partialsortperm(v, k; by=identity, lt=isless, rev=false)

Return a partial permutationI of the vectorv, so thatv[I] returns values of a fully sorted version ofv at indexk. Ifk is a range, a vector of indices is returned; ifk is an integer, a single index is returned. The order is specified using the same keywords assort!. The permutation is stable: the indices of equal elements will appear in ascending order.

This function is equivalent to, but more efficient than, callingsortperm(...)[k].

Examples

julia> v = [3, 1, 2, 1];julia> v[partialsortperm(v, 1)]1julia> p = partialsortperm(v, 1:3)3-element view(::Vector{Int64}, 1:3) with eltype Int64: 2 4 3julia> v[p]3-element Vector{Int64}: 1 1 2

partialsortperm!(ix, v, k; by=identity, lt=isless, rev=false)

Likepartialsortperm, but accepts a preallocated index vectorix the same size asv, which is used to store (a permutation of) the indices ofv.

ix is initialized to contain the indices ofv.

(Typically, the indices ofv will be1:length(v), although ifv has an alternative array type with non-one-based indices, such as anOffsetArray,ix must share those same indices)

Upon return,ix is guaranteed to have the indicesk in their sorted positions, such that

partialsortperm!(ix, v, k);v[ix[k]] == partialsort(v, k)

The return value is thekth element ofix ifk is an integer, or view intoix ifk is a range.

Examples

julia> v = [3, 1, 2, 1];julia> ix = Vector{Int}(undef, 4);julia> partialsortperm!(ix, v, 1)2julia> ix = [1:4;];julia> partialsortperm!(ix, v, 2:3)2-element view(::Vector{Int64}, 2:3) with eltype Int64: 4 3

Base.Order.Ordering

Abstract type which represents a strict weak order on some set of elements. Seesort! for more.

UseBase.Order.lt to compare two elements according to the ordering.

lt(o::Ordering, a, b) -> Bool

Test whethera is less thanb according to the orderingo.

ord(lt, by, rev::Union{Bool, Nothing}, order::Ordering=Forward)

Construct anOrdering object from the same arguments used bysort!. Elements are first transformed by the functionby (which may beidentity) and are then compared according to either the functionlt or an existing orderingorder.lt should beisless or a function that obeys the same rules as thelt parameter ofsort!. Finally, the resulting order is reversed ifrev=true.

Passing anlt other thanisless along with anorder other thanBase.Order.Forward orBase.Order.Reverse is not permitted, otherwise all options are independent and can be used together in all possible combinations.

Base.Order.Forward

Default ordering according toisless.

ReverseOrdering(fwd::Ordering=Forward)

A wrapper which reverses an ordering.

For a givenOrderingo, the following holds for alla,b:

lt(ReverseOrdering(o), a, b) == lt(o, b, a)

Base.Order.Reverse

Reverse ordering according toisless.

By(by, order::Ordering=Forward)

Ordering which appliesorder to elements after they have been transformed by the functionby.

Lt(lt)

Ordering that callslt(a, b) to compare elements.lt must obey the same rules as thelt parameter ofsort!.

Perm(order::Ordering, data::AbstractVector)

Ordering on the indices ofdata wherei is less thanj ifdata[i] is less thandata[j] according toorder. In the case thatdata[i] anddata[j] are equal,i andj are compared by numeric value.