Alternatively, DataStructures.jl has an internal implementation of balanced trees. Given that the Sorted* datastructures use it, it should be pretty well tested, and could serve as the basis for an implementation for SortedArray.
Which datastructure is best depends a lot on the relative frequency of insertions and lookups. Also, depending on problem sizes, constant factors may dominate asymptotic performance considerations. I would just start @dfdx’s suggestion and go from there.
Moreover, if you can put a bound on k ex ante, you can just use an array big enough for that.