For the binary search idea, you could use Leonid Shifrin's fast, compiled binary search function here. It would look like this:
sortedInsert[list_, el_] := Insert[
list,
el,
bsearchMax[list, el]
]
sortedInsert[2 Range[10], 13]
{2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20}
list = Sort@RandomInteger[100000, 10000];
values = RandomInteger[100000, 1000];
sortedInsert[list, #] & /@ values; // RepeatedTiming
{0.018, Null}
You may also want to check out the other solutions in that answer. As some have pointed out, the best complexity solution is not always the most performant solution, when implemented in Mathematica. For comparison with a very naive approach, however, we can clearly see that the above helps:
sortedInsert2[list_, el_] := Insert[
list,
el,
LengthWhile[list, el > # &] + 1
]
sortedInsert2[list, #] & /@ values; // RepeatedTiming
{1.5954, Null}
Nearest is quite a lot faster than the naive approach, but not as fast as binary search. A drawback is that if we're inserting elements into the list, then we need to recreate the NearestFunction over and over since there is no way to update it.
sortedInsert3[list_, el_] := With[
{nf = Nearest[list -> "Index"]},
Insert[
list,
el,
Last@nf[el]
]
]
sortedInsert3[list, #] & /@ values; // RepeatedTiming
{0.24, Null}
I tried running Nearest directly instead of creating a NearestFunction explicitly, but it turned out to be slower.
The second best solution that I've found is the most naive of them all, that you also mention in your question:
Sort[Append[list, #] & /@ values]; // RepeatedTiming
{0.095, Null}
I'm aware that Append does not actually append any value, but neither does Insert so I'm using it for comparison here. Sorting would take a bit longer perhaps if accounting for a large number of newly inserted elements, but as we can see sorting is very fast. If you have all the elements you want to insert available up front, then it's a no-brainer:
Sort@Join[list, values]; // RepeatedTiming
{0.000075, Null}
This reflects the fact that dynamically resizing lists is very slow, so we should typically always try to avoid that under any circumstance, including this one. (In Mathematica we also typically try to avoid any kind of looping, so we can look at it from that point of view too, Map being a type of iteration.)