JuliaCollections / OrderedCollections.jl

Julia implementation of associative containers that preserve insertion order
MIT License
92 stars 38 forks source link

Shortcut in `sort!(::OrderedDict)` if already sorted #103

Closed fredrikekre closed 1 year ago

fredrikekre commented 1 year ago

This patch implements a shortcut in sort!(::OrderedDict) to return early in case the dict is already sorted. This avoids allocation of the permutation vector and new arrays for keys and vals. This optimization exist already in Base for sorting arrays, and checking for sortedness is cheap in comparison to do the sorting.

Note that sort!(x::OrderedSet) already has this optimization implicitly since it uses Base's sort! implementation on (x.dict.keys)::Vector.

fredrikekre commented 1 year ago

Thanks for the review.