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

Question

The main question . What is the fastest way to insert an item into a list that is already sorted using Julia?

I am currently doing 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 avoid duplicates at the same time?

Answer 1

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

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

This is a nice little 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 

It made me think splice! should handle the case where the replacement is a single value, not an array, so I can add this function.