This is merge sorting?

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 .shifting. Plus .shift is called many times in the loop.

1 Like
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.