Merge 2 arrays at specific indices in Javascript

Question

I have a target array, say: [A, C, E, F, H]. I have another array toMerge that needs to be merged into target, say: [B, D, G, I]. I also have an integer array that tells the indices of target array where toMerge items will be finally merged at, say: [1, 3, 6, 8].

I need a function that will merge toMerge array into target in-place, at indices specified by the indices array so that target eventually looks like

[A(0), B(1), C(2), D(3), E(4), F(5), G(6), H(7), I(8)]

I tried using inbuilt array splice functions to iterate over indices array and splice(add) each at each index. Something along the lines:

for (let i = 0; i < indices.length; i++) {
    target.splice(indices[i], 0, toMerge[i]);
}

I am looking for any solution that can do it more efficiently and elegantly.

It gets trickier if the indices array is unsorted or worse - reverse-sorted! For e.g.,

toMerge: [I, G, D, B]
indices: [8, 6, 3, 1]

after applying the above algorithm, target ends up being:

target: [A, B, C, E, D, F, H, I, G]

One solution to this is to sort the indices array in non-decreasing order along with the toMerge array ensuring the sequence is honored, further complicating things.

Answer 1

Unsorted indices + absolute

If you are working with unsorted indices: you would have to "zip" (need to first transpose) the array to be merged and its corresponding indices. Once you have a matrix of [index, value][] sorted, you can perform an in-order splice.

const transpose = (a) => a[0].map((_, i) => a.map(r => r[i]));
const sortByIndex = (a) => a.sort((x, y) => x[0] - y[0]);

const absoluteMerge = (a, toMerge, unsortedIndices) => {
  const res = [...a];
  const sorted = sortByIndex(transpose([unsortedIndices, toMerge]));
  for (let i = 0; i < sorted.length; i++) {
    res.splice(sorted[i][0], 0, sorted[i][1]);
  }
  return res;
};

const a = ['A', 'C', 'E', 'F', 'H'], b = ['I', 'G', 'D', 'B'];

const c = absoluteMerge(a, b, [8, 6, 3, 1]);

console.log(...c); // A B C D E F G H I

---

Original response

If you are working with absolute indices (as you are), you can insert the items in-order; but if you use relative indices, you need to reverse the insertion.

Absolute merge

const absoluteMerge = (a, b, insertionIndices) => {
  const res = [...a];
  for (let i = 0; i < insertionIndices.length; i++) {
    res.splice(insertionIndices[i], 0, b[i]);
  }
  return res;
};

const a = ['A', 'C', 'E', 'F', 'H'], b = ['B', 'D', 'G'];

const c = absoluteMerge(a, b, [1, 3, 6]);

console.log(...c); // A B C D E F G H

Relative merge

const relativeMerge = (a, b, insertionIndices) => {
  const res = [...a];
  for (let i = insertionIndices.length - 1; i >= 0; i--) {
    res.splice(insertionIndices[i], 0, b[i]);
  }
  return res;
};

const a = ['A', 'C', 'E', 'F', 'H'], b = ['B', 'D', 'G'];

const c = relativeMerge(a, b, [1, 2, 4]);

console.log(...c); // A B C D E F G H

Answer 2

Thinking on sorted, reverse-sorted, and a possibility of unsorted list toMerge, at first we need to merge the toMerge with the indices list and sort, then we can merge these values with the target list, for example:

const mergeArraysByIndex = (target, toMerge, indices) => {
  // Create an array of objects with keys and values
  const toMergeWithIndex = toMerge.map((key, index) => ({key, value: indices[index]}));

  // Sort the array of objects by value
  toMergeWithIndex.sort((a, b) => a.value - b.value);

  // Create a final object with sorted keys and values
  const resultObject = {};
  toMergeWithIndex.forEach(item => {
    resultObject[item.key] = item.value;
  });

  //Merge the arrays together
  return Object.values(resultObject).reduce((acc, index, i) => {
    acc.splice(index, 0, Object.keys(resultObject)[i]);
    return acc;
  }, [...target])
}

//First example (sorted!)
console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['B', 'D', 'G'], [1, 3, 6]));

//Second example (reverse-sorted!)
console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['I', 'G', 'D', 'B'], [8, 6, 3, 1]));

//Third example (unsorted!)
console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['D', 'I', 'G', 'B'], [3, 8, 6, 1]));

Or in a resumed way:

const mergeArraysByIndex = (target, toMerge, indices) => {
  return indices
    .map((index, i) => ({ key: toMerge[i], index }))
    .sort((a, b) => a.index - b.index)
    .reduce((acc, { key, index }) => {
      acc.splice(index, 0, key);
      return acc;
    }, [...target]);
};

//First example (sorted!)
console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['B', 'D', 'G'], [1, 3, 6]));

//Second example (reverse-sorted!)
console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['I', 'G', 'D', 'B'], [8, 6, 3, 1]));

//Third example (unsorted!)
console.log(mergeArraysByIndex(['A', 'C', 'E', 'F', 'H'], ['D', 'I', 'G', 'B'], [3, 8, 6, 1]));

Answer 3

An one-liner with sorting the indices and toMerge:

const target = [...'ACEFH'], toMerge = [...'IGDB'], indices = [8,6,3,1];

toMerge.map((c,i) => [indices[i],c]).sort(([a],[b]) => a-b).forEach(([i, c]) => target.splice(i, 0, c));

console.log(...target);

Cycles: 1000000 / Chrome/117
-----------------------------------------
Alexander   193/min  1.0x  203  215  193
Polywhirl   218/min  1.1x  230  257  218
-----------------------------------------
https://github.com/silentmantra/benchmark

<script benchmark="1000000">

const toMerge = [...'IGDB'], indices = [8,6,3,1];

// @benchmark Polywhirl
const transpose = (a) => a[0].map((_, i) => a.map(r => r[i]));
const sortByIndex = (a) => a.sort((x, y) => x[0] - y[0]);

const absoluteMerge = (a, toMerge, unsortedIndices) => {
  const res = [...a];
  const sorted = sortByIndex(transpose([unsortedIndices, toMerge]));
  for (let i = 0; i < sorted.length; i++) {
    res.splice(sorted[i][0], 0, sorted[i][1]);
  }
  return res;
};

absoluteMerge([...'ACEFH'], toMerge, indices);

// @benchmark Alexander
const target = [...'ACEFH'];
toMerge.map((c,i) => [indices[i],c]).sort(([a],[b]) => a-b).forEach(([i, c]) => target.splice(i, 0, c));
target;
</script>
<script src="https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js"></script>