Return to Answer

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:

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:

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

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"]
  ]

Original Method

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}, {Join[pos, Range@no]}\[Transpose]}, Join[val, 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