# This is merge sorting?

**URL:** <https://forum.freecodecamp.org/t/this-is-merge-sorting/29350>\
**Category:** General\
**Created:** [August 19, 2016, 1:06am UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350 "2016-08-19T01:06:37Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![IAmMyself](https://avatars.discourse-cdn.com/v4/letter/i/49beb7/32.png) [@IAmMyself](https://forum.freecodecamp.org/u/IAmMyself)\
**Post date:** [August 19, 2016, 1:06am UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/1 "2016-08-19T01:06:37Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kevcomedia](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/kevcomedia/32/125737_2.png) [@kevcomedia](https://forum.freecodecamp.org/u/kevcomedia)\
**Post date:** [August 19, 2016, 4:15am UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/2 "2016-08-19T04:15:32Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![IAmMyself](https://avatars.discourse-cdn.com/v4/letter/i/49beb7/32.png) [@IAmMyself](https://forum.freecodecamp.org/u/IAmMyself)\
**Post date:** [August 19, 2016, 1:02pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/3 "2016-08-19T13:02:26Z")

</div>

@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](https://repl.it/CopU/3) now a valid [merge sorting](https://en.wikipedia.org/wiki/Merge_sort) algorithm?

---

<div class="post-metadata">

**Author:** ![kevcomedia](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/kevcomedia/32/125737_2.png) [@kevcomedia](https://forum.freecodecamp.org/u/kevcomedia)\
**Post date:** [August 19, 2016, 1:21pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/4 "2016-08-19T13:21:40Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![IAmMyself](https://avatars.discourse-cdn.com/v4/letter/i/49beb7/32.png) [@IAmMyself](https://forum.freecodecamp.org/u/IAmMyself)\
**Post date:** [August 19, 2016, 1:25pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/5 "2016-08-19T13:25:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kevcomedia](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/kevcomedia/32/125737_2.png) [@kevcomedia](https://forum.freecodecamp.org/u/kevcomedia)\
**Post date:** [August 19, 2016, 1:35pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/6 "2016-08-19T13:35:27Z")

</div>

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

```javascript
  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;

```

---

<div class="post-metadata">

**Author:** ![IAmMyself](https://avatars.discourse-cdn.com/v4/letter/i/49beb7/32.png) [@IAmMyself](https://forum.freecodecamp.org/u/IAmMyself)\
**Post date:** [August 19, 2016, 2:04pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/7 "2016-08-19T14:04:48Z")

</div>

@kevcomedia Can you look at [this](https://repl.it/CopU/8), and tell me what you think about it now.

---

<div class="post-metadata">

**Author:** ![kevcomedia](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/kevcomedia/32/125737_2.png) [@kevcomedia](https://forum.freecodecamp.org/u/kevcomedia)\
**Post date:** [August 19, 2016, 2:24pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/8 "2016-08-19T14:24:09Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![IAmMyself](https://avatars.discourse-cdn.com/v4/letter/i/49beb7/32.png) [@IAmMyself](https://forum.freecodecamp.org/u/IAmMyself)\
**Post date:** [August 19, 2016, 2:31pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/9 "2016-08-19T14:31:08Z")

</div>

@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](https://repl.it/CopU/10).

---

<div class="post-metadata">

**Author:** ![kevcomedia](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/kevcomedia/32/125737_2.png) [@kevcomedia](https://forum.freecodecamp.org/u/kevcomedia)\
**Post date:** [August 19, 2016, 2:35pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/10 "2016-08-19T14:35:02Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![IAmMyself](https://avatars.discourse-cdn.com/v4/letter/i/49beb7/32.png) [@IAmMyself](https://forum.freecodecamp.org/u/IAmMyself)\
**Post date:** [August 19, 2016, 2:39pm UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/11 "2016-08-19T14:39:03Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jwilkins.oboe](https://sea3.discourse-cdn.com/freecodecamp/user_avatar/forum.freecodecamp.org/jwilkins.oboe/32/179497_2.png) [@jwilkins.oboe](https://forum.freecodecamp.org/u/jwilkins.oboe)\
**Post date:** [January 16, 2021, 4:41am UTC](https://forum.freecodecamp.org/t/this-is-merge-sorting/29350/12 "2021-01-16T04:41:24Z")

</div>

Closed on January 16, 2021, 4:41am UTC