Looking for a way to insert multiple elements into multiple positions simultaneously in a list

New developments

rasher posted a new answer with clean and well performing code that caused me to look again at this problem. (It well deserves your vote.) I see now that there are good ways to approach this problem that haven't yet been fully developed. Fundamentally rasher's code operates by Sort, but I don't think even he realized this as Riffle et al are superfluous. We merely need Ordering and Part applied to joined lists of the correct order:

oInsert[list_, val_, pos_] :=
  Join[val, list][[ Ordering @ Join[pos, Range @ Length @ list] ]]

In a way rasher solved the problem twice: Riffle and sa[[ps]] = reps already place the elements in the proper order; one merely needs to get rid of the zeros. We could use DeleteCases but pattern based methods are slow. Instead I reimplemented the Riffle operation in terms of SparseArray, but to make it efficient I had to be clever and unfortunately here that (so far) implies less clean code.

saInsert[list_, val_, pos_] :=
  With[{no = Length[list], ni = Length[val]},
    SparseArray[
      Automatic, {2, no + 1}, 0,
      {1, {{0, ni, no + ni}, pos ~Join~ Range[no] ~Partition~ 1}, val ~Join~ list}
    ]\[Transpose]["NonzeroValues"]
  ]

This ugly bit of code manually constructs a two row SparseArray, the upper row being the insertion elements and the lower being the original list. It then transposes them, and extracts the "NonzeroValues". (Despite the name these are actually the non-background values; this code still works correctly with zeros.)

Rudimentary test of both new methods:

oInsert[{a, b, c, d, e}, {W, X, Y, Z}, {1, 2, 4, 6}]

saInsert[{a, b, c, d, e}, {W, X, Y, Z}, {1, 2, 4, 6}]

{W, a, X, b, c, Y, d, e, Z}

{W, a, X, b, c, Y, d, e, Z}

I shall add timings for these functions later, but to summarize my early findings:

• multiInsert2 is still the fastest for a limited number of insertions into a long list
• saInsert is superior to all other methods posted so far for a greater number of insertions into a packed list
• oInsert is competitive with saInsert and rashernator on unpacked lists. It is faster than rashernator on packed lists.

---

Original Method

If your list is a vector (has no sub-lists) this is perhaps the simplest way, and likely competitively fast:

m = origlist;

m[[{1, 5}]] = {{r, x}, m[[{1, 5}]]}\[Transpose]

Flatten[m]

{r, a, b, c, d, x, e, f, g}

Edit: Ray Koopman points out that this method, by itself, does not handle an edge case in Insert where the position is one greater than the length of the list, i.e. Insert[{1,2,3}, x, 4]. This is accounted for in the function below by padding the list as required.

If your list is not a vector (as defined above) we could use a different head for the inserted elements and then replace it with Sequence to effect a flatten. Here is a function that handles both cases, selecting between the methods for best performance:

multiInsert[list_List, val_, pos_] /; Length@val == Length@pos :=
  Module[{m = list, f, pad},
    pad[x_] /; Max@pos == Length@list + 1 := AppendTo[m, x];
    If[VectorQ[val] && VectorQ[list],
      pad[{ }]; m[[pos]] = Transpose @ {val, m[[pos]]}; Flatten[m],
      pad[f[]]; m[[pos]] = MapThread[f, {val, m[[pos]]}]; m /. f -> Sequence
    ]
  ]

Input is a little different from yours:

multiInsert[Range@15, {a, b, c}, {3, 7, 13}]

{1, 2, a, 3, 4, 5, 6, b, 7, 8, 9, 10, 11, 12, c, 13, 14, 15}

Preallocate Method

Nasser proposed a method of preallocating the array. This idea was promising if it could be optimized because a packed array could be preserved throughout the process theoretically reducing memory and computation time. His implementation was limited in performance because it used a tag that necessitated unpacking and because searching for that tag using Position is slow. Here is an implementation that directly calculates the runs of original values rather than tagging and finding them afterward.

multiInsert2[list_, val_, pos_] /; Length@val == Length@pos :=
  Module[{new, start, end, offset, n1, n2},
    {n1, n2} = Length /@ {list, val};
    new    = ConstantArray[0, n1 + n2];
    start  = Prepend[pos, 1];
    end    = Append[pos - 1, n1];
    offset = Range[0, n2];
    MapThread[
      new[[# ;; #2]] = list[[#3 ;; #4]]; &,
      {offset + start, offset + end, start, end}
    ];
    new[[pos + Range[0, n2 - 1]]] = val;
    new
  ]

This function appear to be best for a moderate number of insertions into a long list. (See below)

Notes and timings

Ray Koopman posted a very elegant method, which on reflection I've seen before though I cannot remember where. I voted for that method but there is reason to use the longer forms that belisarius and I proposed: speed on long lists. Every Insert operation reallocates the array which takes time proportional to the length of the list. As such, a method using Fold will slow down considerably when doing many insertions into a very long list. I will call Ray Koopman's code foldInsert:

foldInsert[list_, val_, pos_] /; Length@val == Length@pos :=
 Fold[
  Insert[#1, #2[[2]], #2[[1]]] &,
  list,
  Reverse @ Sort @ Transpose @ {pos, val}
 ]

And using this timing code for the three functions multiInsert, multiInsert2, foldInsert:

timeAvg = 
  Function[func,
    Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}],
    HoldFirst];

time[n_Integer, k_Integer, rand_: RandomInteger] :=
 Module[{start, vals, pos},
  start = Range@n;
  vals = rand[9, k];
  pos = Sort @ RandomSample[start, k];
  timeAvg @ #[start, vals, pos] & /@ {multiInsert, multiInsert2, foldInsert}
]

With 3500 insertions into a length 5000 list:

time[5000, 3500]

{0.0017968, 0.007368, 0.01372}

With five insertions into a length 500,000 list:

time[500000, 5]

{0.02432, 0.0006736, 0.001448}

With 7500 insertions into the length 500,000 list:

time[500000, 7500]

{0.03244, 0.01812, 5.038}

All timings above were performing with integer into integer insertions. If inserting reals unpacking is necessary. Here are a few timings for that situation:

time[150000, 50, RandomReal]
time[150000, 500, RandomReal]
time[150000, 5000, RandomReal]

{0.01372, 0.005488, 0.0624}

{0.01308, 0.007368, 0.592}

{0.01684, 0.01748, 8.658}

Building on Kuba's answer: If you insert in reverse order then the positions don't need to be incremented.

Fold[Insert[#1,#2[[2]],#2[[1]]]&, origlist,  
     Reverse@Sort@Transpose@{insertpositions,insertvalues}]  

If a value is to be inserted in several positions then it must be appear in insertvalues once for each position. Elements of insertvalues may themselves be lists.

Probably also:

pInsert[origList_, repList_] := 
      Function[{l}, ReplacePart[
                      l, 
                      Thread[Rule[#[[1]], Sequence[#[[2]], l[[#[[1]]]]]] &/@ repList]]]@origList

pInsert[{a, b, c, d, e}, {{2, {x, y}}, {5, z}}]

{a, {x, y}, b, c, d, z, e}