A bit off, but still worth considering.
Where does your data to insert come from, and when do you need to use it?
Typically, either you have the data upfront, before actually using it (e.g. on disk) or the data slowly comes while also being processed (e.g. user input, sensors, network).
In the first case, maybe first load all data without inserting to the right place and sort the array once before use.
In the second case, unless talking about very large data sets, the input is slow enough to do whatever insert method you want.