Repository: JuliaLang/julia
File: base/sort.jl (Julia)

Code before:
    show_type(io, alg)
    print(io, '(')
    for (i, name) in enumerate(fieldnames(typeof(alg)))
        arg = getproperty(alg, name)
        i > 1 && print(io, ',')
        if arg isa Algorithm
            println(io)
            print_tree(io, arg, cols+1)
        else
            i > 1 && print(io, ' ')
            print(io, arg)
        end
    end
    print(io, ')')
end
show_type(io::IO, alg::Algorithm) = Base.show_type_name(io, typeof(alg).name)
show_type(io::IO, alg::Small{N}) where N = print(io, "Base.Sort.Small{$N}")

defalg(v::AbstractArray) = DEFAULT_STABLE
defalg(v::AbstractArray{<:Union{Number, Missing}}) = DEFAULT_UNSTABLE
defalg(v::AbstractArray{Missing}) = DEFAULT_UNSTABLE # for method disambiguation
defalg(v::AbstractArray{Union{}}) = DEFAULT_UNSTABLE # for method disambiguation
defalg(v) = DEFAULT_STABLE

"""
    sort!(v; alg::Base.Sort.Algorithm=Base.Sort.defalg(v), lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Base.Order.Ordering=Base.Order.Forward)

Mutate the vector `v` so that it is sorted.

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](@ref) 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 implementation 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`](@ref) or [`Base.Order.Reverse`](@ref) 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](@ref).

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.

Review comment (performance):
Documenting `rev::Bool=false` is a lie, but it is a pretty reasonable lie to lie. `rev::Bool` is the API we want, `rev::Union{Bool, Nothing}=nothing` where `nothing` is an alias for `false` is a cludgy performance workaround that could hopefully someday (maybe already) be removed when constant propagation is sufficient.

If we do change this here (and elsewhere in sorting), we need to document what `nothing` means.

Code after:
    show_type(io, alg)
    print(io, '(')
    for (i, name) in enumerate(fieldnames(typeof(alg)))
        arg = getproperty(alg, name)
        i > 1 && print(io, ',')
        if arg isa Algorithm
            println(io)
            print_tree(io, arg, cols+1)
        else
            i > 1 && print(io, ' ')
            print(io, arg)
        end
    end
    print(io, ')')
end
show_type(io::IO, alg::Algorithm) = Base.show_type_name(io, typeof(alg).name)
show_type(io::IO, alg::Small{N}) where N = print(io, "Base.Sort.Small{$N}")

defalg(v::AbstractArray) = DEFAULT_STABLE
defalg(v::AbstractArray{<:Union{Number, Missing}}) = DEFAULT_UNSTABLE
defalg(v::AbstractArray{Missing}) = DEFAULT_UNSTABLE # for method disambiguation
defalg(v::AbstractArray{Union{}}) = DEFAULT_UNSTABLE # for method disambiguation
defalg(v) = DEFAULT_STABLE

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

Mutate the vector `v` so that it is sorted.

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](@ref) 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 implementation 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`](@ref) or [`Base.Order.Reverse`](@ref) 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](@ref).

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.