Insert item into a sorted list with Julia (with and without duplicates)

Question

Main Question: What is the fastest way to insert an item into a list that is already sorted using Julia?

Currently, I do this:

v = [1, 2, 3, 5] #example list
x = 4 #value to insert
index = searchsortedfirst(v, x) #find index at which to insert x
insert!(v, index, x) #insert x at index

Bonus Question: What if I want to simultaneously ensure no duplicates?

Answer 1

You can use searchsorted to get the range of indices where the value occurs instead of just the first one and then use splice! to replace the values in that range with a new set of values:

insert_and_dedup!(v::Vector, x) = (splice!(v, searchsorted(v,x), [x]); v)

That's a nice little one-liner that does what you want.

julia> v = [1, 2, 3, 3, 5];

julia> insert_and_dedup!(v, 4)
6-element Array{Int64,1}:
 1
 2
 3
 3
 4
 5

julia> insert_and_dedup!(v, 3)
5-element Array{Int64,1}:
 1
 2
 3
 4
 5

This made me think that splice! should handle the case where the replacement is a single value rather than an array, so I may add that feature.