Return to Answer

Array#splice, Array#unshift will need to move all following element in the list. So it runs under \$O(n)\$ in your case. Your algorithm runs in \$O(n^2)\$ then. But a merge sort should be run in \$O(\log n)\$. As you know... You can write a even shorter code if you try to use Bubble sort as long as you don't care about time complexity.

You can see that your time usage is \$O(n^2)\$ instead of \$O(\log n)\$.

Array#splice, Array#unshift will need to move all following element in the list. So it runs under \$O(n)\$ in your case. Your algorithm runs in \$O(n^2)\$ then. But a merge sort should be run in \$O(n \log n)\$. As you know... You can write a even shorter code if you try to use Bubble sort as long as you don't care about time complexity.

You can see that your time usage is \$O(n^2)\$ instead of \$O(n \log n)\$.

Array#splice will need to move all following element in the list. So it runs under \$O(n)\$ in your case. Your algorithm runs in \$O(n^2)\$ then. But a merge sort should be run in \$O(\log n)\$. As you know... You can write a even shorter code if you try to use Bubble sort as long as you don't care about time complexity.

Array#splice, Array#unshift will need to move all following element in the list. So it runs under \$O(n)\$ in your case. Your algorithm runs in \$O(n^2)\$ then. But a merge sort should be run in \$O(\log n)\$. As you know... You can write a even shorter code if you try to use Bubble sort as long as you don't care about time complexity.

for (i = 1; i <= 10; ++i) {
  const time = []
  const size = i * 1e3;
  for (let i = 0; i < 11; i++) {
    const arr = [...Array(size)].map(_ => Math.random());
    const t0 = performance.now();
    mergeSort(arr);
    const t = performance.now() - t0;
    time.push(t);
  }
  const mid = time.sort((x, y) => x - y)[5];
  console.log("%o\t%o", size, +mid.toFixed(2));
}

Your merge function didn't keep the stable order. However this can be fixed by changing lista[0] < listb[0] to lista[0] <= listb[0].

After that, the merge sort is still unstable. Consider 3 elements input [a, b, c]. What you do is actually merge([c], merge([a], [b])). But it should be merge(merge([a], [b]), [c]). The order here is important as otherwise sort stability will not be held any more.

const arr = [1, 1, 1].map(Object)
const ori = [...arr];
const result = mergeSort(arr);
console.log(result.map(x => ori.indexOf(x))) // [1, 0, 2]