# This is merge sorting?

This is merge sorting?
0

#1

Can somebody help diagnose what’s wrong with my implementation of merge sorting? https://repl.it/CopU/2

#2

It’s tricky to sort floating points. Use `Math.floor(Math.random() * 2000) - 1000` for now, so you get integers.

In the `actualSorter` function, the `return` is inside the for-loop, so the value is prematurely returned.

In the `mergeSort` function you might have meant to use `slice` instead of `splice`.

#3

@kevcomedia Thanks! I had it working before, but I lost my code and had to re-write it. I looked at it for an hour, but it gets really hard to look for bugs after you’ve finished a project.

Also, is this now a valid merge sorting algorithm?

#4

I don’t think so. I timed your sorting function, and I got these times, which seem really slow for merge sort:

``````     n          ms        built-im ms
1000          8                  0
10000        455                  5
100000      24441                 60
1000000         -                 778
``````

#5

@kevcomedia That’s what I was thinking, but I’m not really sure why it’s so slow. It looks to me, from the description of merge sort, that mine should be a merge sort algorithm.

#6

It’s probably in your implementation. I wrote a version that can comfortably sort 2,000,000 elements (if you’re willing to wait around 6 seconds, that is). The code is rather crude though

``````  var value = [];
var i = 0;
var j = 0;
while (i < arr.length && j < arr2.length) {
if (arr[i] < arr2[j]) {
value.push(arr[i]);
i++;
}
else {
value.push(arr2[j]);
j++;
}
}

if (i == arr.length) {
for (j; j < arr2.length; j++) {
value.push(arr2[j]);
}
}
else {
for (i; i < arr.length; i++) {
value.push(arr[i]);
}
}

return value;
``````

#7

@kevcomedia Can you look at this, and tell me what you think about it now.

#8

I tried switching back to using `.splice`, then used `arr` alone in the second `mergeSort` call (since after splicing, it’s just the second half of the original array anyway)

``````actualSorter(mergeSort(arr.splice(0, length / 2)), mergeSort(arr));
``````

It’s a bit faster (after testing for 3 million elements, this version cut down sorting time from 10s to 8s).

Honestly I can’t think of any other way to cut down sorting time. I’ll try making a version that doesn’t split up the array, and see if that’s faster.

#9

@kevcomedia I think that the problem was that I was using a `for` loop, because after switching to a `while` loop, it is quite a bit faster. (I also switched to `.splice` and `arr`) Would you take a look.

#10

I don’t blame it to the for-loop, but I blame it to the `shift` calls in the for-loop. This is just speculation, but I think it’s slow because it shifts the indexes of every element after `.shift`ing. Plus `.shift` is called many times in the loop.

#11

@kevcomedia That makes sense. Wow! Yeah, I didn’t think of that. Also, it’s regularly clocking in under 0.5 seconds to sort 2,000,000 elements, so I think it’s working.

Thanks for the help.