Best way to insert element into an ordered list at the correct position?

Question

Suppose I have an ordered list orderedList and I want to write some code that will involve regularly inserting new elements into orderedList in the correct positions, according to the ordering. One possibility is

Sort[AppendTo[orderedList,x]],

but this is inefficient because Mathematica doesn't know orderedList is already ordered, hence it will waste time verifying that the original elements of orderedList are already ordered.

Another idea is to use SelectFirst to obtain the proper position at which to insert x, via

Insert[orderedList,x,FirstPosition[SelectFirst[orderedList,#>x&]]].

The trouble here is that since Mathematica doesn't know orderedList is ordered, its SelectFirst algorithm will use a linear search rather than binary. Also, the requirement of using FirstPosition will double the computation time.

So what is the "right" way to do this, i.e., what method inserts an element into an ordered list without wasting resources?

Answer 1

If you have v12.1, there's no need to ever call Sort if you can incrementally add your values to a "PriorityQueue" data structure. It always stays sorted as you add/remove elements.

SeedRandom[1234];
ds = CreateDataStructure["PriorityQueue"];
(* push a million random values in - use Scan for pushing many values. 
 The slowest part here is creating RandomIntegers, not the Push which is very fast *)
Scan[ds["Push", #] &, RandomInteger[10^6, 10^6]];
(* peek at the largest value *)
ds["Peek"]
(* returns: 999999 *)

(* add more values *)
ds["Push", N[Sqrt[2]]];
ds["Push", N[π^2]];
ds["Push", 0];

(* get all of the values out and show the first 50 *)
tbl = Reverse@Table[ds["Pop"], {ds["Length"]}];
tbl[[;; 20]]
(* result: {0, 0, 0, 0, 1.41421, 3, 5, 6, 8, 8, 9, 9, 9.8696, 10, 11, 14, 16, 17, 18, 19} *) 

(* After we popped the values, the heap is empty *)
ds["EmptyQ"] (* returns True *)

The timing of each "Push" is extremely small, around 5.*10^-7 on my machine. To get average push time:

rnd = RandomInteger[10^6, 10^6];
First[CompoundExpression[ds["DropAll"], Scan[ds["Push", #] &, rnd]] //
    RepeatedTiming]/10^6
(* 5.*10^-7 per push, overall 0.5 seconds to push 1M values *)

Answer 2

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.)