Insert value into sorted array with fixed size

General Usage
,
2

I think your idea to avoid resizing the array is sensible (although probably not a huge win), and being able to work with MArrays is a good idea too. However, your second option loses some benefit by doing a linear search over the entire collection, when that might not actually be necessary. It also has a branch inside the inner loop, which may interfere with your CPUs pipelining and branch prediction.

Perhaps you could instead do:

  1. Use searchsortedlast to find the right place to put the value
  2. Use copyto! (or a for loop) to shift the data after that index by one to make room.
  3. Put the new value into the space you’ve just made

On the other hand, if you’re dealing with lots of sorted data, you might be better off using a different data structure entirely, like the ones from Sorted Containers · DataStructures.jl

Alternatively, if your collections are small, there may be no advantage to using searchsortedlast, in which case your second option may actually be optimal.

Edit: But you can probably save some time using the usual @inbounds stuff from Performance Tips · The Julia Language

1 Like