1
\$\begingroup\$

I think I programmed a bottom-up merge sort, but I'm a little sceptical that it will work under any data set. By now, I've tested it with many random arrays of massive lengths, and it seems to work; the only thing making me doubt my function is that whenever I look online for a non-recursive one, all of the algorithms by other people are much longer than mine (in terms of the number of lines of code). This makes me suspect I have missed out something important form my function. Here is my work:

function mergeSort(list) {
    list = list.map(n => [n]);  
    while(list.length > 1) {
        list.push(merge(list[0], list[1]));
        list.splice(0, 2);
    }
    return list[0];
}

the merge function is here:

function merge(lista, listb) {
    let newList = new Array();
    while(lista.length && listb.length) {
        const listToProcess = lista[0] < listb[0] ? lista : listb;
        newList.push(listToProcess[0]);
        listToProcess.shift();
    }
    const listWithRemainingElmnts = lista.length ? lista : listb;
    newList = newList.concat(listWithRemainingElmnts);
    return newList;
}

Why are all of the online examples of bottom-up MergeSort so large compared to mine?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

Yes, it is short. But it is somehow incorrect.

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(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.

Try to run your code on my laptop*, time usage is show in table below

Array Size Time Used (ms) Time/Size2 Time/(Size*log(Size))
3000 9.6 1.06e-6 0.92e-3
4000 16.97 1.06e-6 1.17e-3
5000 26.42 1.06e-6 1.42e-3
6000 37.8 1.05e-6 1.66e-3
7000 50.66 1.03e-6 1.88e-3
8000 66.86 1.04e-6 2.14e-3
9000 83.02 1.02e-6 2.33e-3

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

* I'm using node v16.13.0 just in case.

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));
}

Sort Stability

Merge sort should be stable. But yours is not.

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]
\$\endgroup\$
3
  • \$\begingroup\$ Thank you for the answer. If I replace splice(0,2) by shift() which is much faster in chrome, and instead of pushing the merged list I replace the 1st element with it, will that decrease time usage and stabilise the sort function? Because now the merged list is going at the start instead of at the end, and shift() is quite fast to compute, and I'll only be using one shift Instead of 2. \$\endgroup\$
    – Krokodil
    Dec 6, 2021 at 8:40
  • \$\begingroup\$ @AlphaHowl Both shift, unshift, splice cost O(n). So no, it will not be faster. Also, pushing merge result to front instead of back makes it much worse: it becomes insert sort. \$\endgroup\$
    – tsh
    Dec 6, 2021 at 9:20
  • \$\begingroup\$ @AlphaHowl to improve time complexity, you can use a linked list based queue instead. But for stability, maybe you need to rewrite your code in some other ways. \$\endgroup\$
    – tsh
    Dec 6, 2021 at 9:32
0
\$\begingroup\$

Most code you find online has been written to explain how bottom-up merge sort works. They specifically avoid writing compact code.

Writing compact code can be fun, and has a competitive element to it. You might like sites like HackerRank or CodeWars.

When writing code which will actually be used in an production environment, length of code is not an important criterion. Important criteria are: Can someone else easily understand it? Can I understand this code 6 years from now? Is it robust? Properly tested? Is it efficient? In this case I would use sort(). 😉

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.