Merge two sorted lists (remove duplicate elements) (v4)

Revision 4 of this benchmark created on April 26, 2024

Description

Setup

var list1 = [];
var list2 = [];
for (let x = 0; x < 200; x++) {
  list1.push(Math.floor(Math.random() * 1000));
  list2.push(Math.floor(Math.random() * 1000));
}
var intAsc = (a, b) => a - b;
list1.sort(intAsc);
list2.sort(intAsc);

function findIndex_Splice(list, item) {
  let idx = list.findIndex((e) => e >= item);
  if (idx === -1) {
    list.push(item);
  } else if (list[idx] > item) { // not equal
    list.splice(idx, 0, item); // insert
  }
  return list;
}

function filterMerge(list1, list2) {
  let list3 = [...list1, ...list2].sort(intAsc);
  return list3.filter((item, index) => !index || item !== list3[index - 1]);
}

function setMerge(list1, list2) {
  return [...new Set([...list1, ...list2])].sort(intAsc);
}

function zipperMerge(list1, list2) {
  let list3 = [];
  let idx1 = 0, idx2 = 0;
  while (idx1 < list1.length && idx2 < list2.length) {
    if (list1[idx1] <= list2[idx2]) {
      if (!list3.length || list3[list3.length - 1] < list1[idx1]) {
        list3.push(list1[idx1]);
      }
      idx1++;
    } else {
      if (!list3.length || list3[list3.length - 1] < list2[idx2]) {
        list3.push(list2[idx2]);
      }
      idx2++;
    }
  }
  while (idx1 < list1.length) {
    if (!list3.length || list3[list3.length - 1] < list1[idx1]) {
      list3.push(list1[idx1]);
    }
    idx1++;
  }
  while (idx2 < list2.length) {
    if (!list3.length || list3[list3.length - 1] < list2[idx2]) {
      list3.push(list2[idx2]);
    }
    idx2++;
  }
  return list3;
}

function zipperMerge2(list1, list2) {
  if (!list1.length && !list2.length) return [];
  if (!list1.length) return [...list2];
  if (!list2.length) return [...list1];

  let list3 = [Math.min(list1[0], list2[0])];
  let idx1 = 0, idx2 = 0;
  while (idx1 < list1.length || idx2 < list2.length) {
    if (idx2 === list2.length || list1[idx1] <= list2[idx2]) {
      if (list3[list3.length - 1] < list1[idx1]) {
        list3.push(list1[idx1]);
      }
      idx1++;
    } else if (idx1 === list1.length || list2[idx2] <= list1[idx1]) {
      if (list3[list3.length - 1] < list2[idx2]) {
        list3.push(list2[idx2]);
      }
      idx2++;
    }
  }
  return list3;
}

function zipperMerge3(list1, list2) {
  let list3 = [];
  let idx1 = 0, idx2 = 0;
  while (idx1 < list1.length || idx2 < list2.length) {
    if (idx2 === list2.length || list1[idx1] <= list2[idx2]) {
      if (!list3.length || list3[list3.length - 1] < list1[idx1]) {
        list3.push(list1[idx1]);
      }
      idx1++;
    } else if (idx1 === list1.length || list2[idx2] <= list1[idx1]) {
      if (!list3.length || list3[list3.length - 1] < list2[idx2]) {
        list3.push(list2[idx2]);
      }
      idx2++;
    }
  }
  return list3;
}

function zipperMerge4(list1, list2) {
  if (!list1.length && !list2.length) return [];
  if (!list1.length) return [...list2];
  if (!list2.length) return [...list1];

  let list3 = [Math.min(list1[0], list2[0])];
  let idx1 = 0, idx2 = 0;
  while (idx1 < list1.length && idx2 < list2.length) {
    if (list1[idx1] <= list2[idx2]) {
      if (list3[list3.length - 1] < list1[idx1]) {
        list3.push(list1[idx1]);
      }
      idx1++;
    } else {
      if (list3[list3.length - 1] < list2[idx2]) {
        list3.push(list2[idx2]);
      }
      idx2++;
    }
  }
  while (idx1 < list1.length) {
    if (list3[list3.length - 1] < list1[idx1]) {
      list3.push(list1[idx1]);
    }
    idx1++;
  }
  while (idx2 < list2.length) {
    if (list3[list3.length - 1] < list2[idx2]) {
      list3.push(list2[idx2]);
    }
    idx2++;
  }
  return list3;
}

function zipperMerge5(list1, list2) {
  if (!list1.length && !list2.length) return [];
  if (!list1.length) return [...list2];
  if (!list2.length) return [...list1];

  let list3 = [Math.min(list1[0], list2[0])];
  let idx1 = 0, idx2 = 0;
  while (idx1 < list1.length && idx2 < list2.length) {
    const item1 = list1[idx1];
    const item2 = list2[idx2];
    const item3 = list3[list3.length - 1];
    if (item1 <= item2) {
      if (item3 < item1) list3.push(item1);
      idx1++;
    } else {
      if (item3 < item2) list3.push(item2);
      idx2++;
    }
  }
  while (idx1 < list1.length) {
    if (list3[list3.length - 1] < list1[idx1]) list3.push(list1[idx1]);
    idx1++;
  }
  while (idx2 < list2.length) {
    if (list3[list3.length - 1] < list2[idx2]) list3.push(list2[idx2]);
    idx2++;
  }
  return list3;
}

Test runner

let list = [...list1];
for (let item of list2) {
  findIndex_Splice(list, item);
}

let list3 = filterMerge(list1, list2);

let list3 = setMerge(list1, list2);

let list3 = zipperMerge(list1, list2);

let list3 = zipperMerge2(list1, list2);

let list3 = zipperMerge3(list1, list2);

let list3 = zipperMerge4(list1, list2);

let list3 = zipperMerge5(list1, list2);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on April 26, 2024
• Revision 2: published on April 26, 2024
• Revision 3: published on April 26, 2024
• Revision 4: published on April 26, 2024