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

Reset to default
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\$ Commented 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\$ Commented 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\$ Commented 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\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.