# Mergesort in JavaScript

**URL:** <https://forum.kirupa.com/t/mergesort-in-javascript/633196>\
**Category:** web dev\
**Created:** [May 16, 2015, 2:04pm UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196 "2015-05-16T14:04:08Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [May 16, 2015, 2:04pm UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196/1 "2015-05-16T14:04:08Z")

</div>

I’m planning on writing my next tutorial on this, but in the meantime, I figured I’ll share my implementation with all of you for now:

```
function mergeSort(input) {
  // can't divide further
  if (input.length < 2) {
    return input;
  }

  // divide
  var mid = Math.floor(input.length / 2);
  var left = mergeSort(input.slice(0, mid));
  var right = mergeSort(input.slice(mid));

  // recursively sort and merge
  return merge(left, right);
}

function merge(left, right) {
  var result = [];

  // order the sublist as part of merging
  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  // add the remaining items to the result
  while (left.length > 0) {
    result.push(left.shift());
  }

  while (right.length > 0) {
    result.push(right.shift());
  }

  // the sorted sublist
  return result;
}

var example = [4, 10, 11, 20, 5, 3, 4, 1, -20, 6];
// console.log(mergeSort(example));

```

This isn’t iterative and doesn’t do any in-place optimizations. It’s recursive 😛

Cheers,  
Kirupa

---

<div class="post-metadata">

**Author:** ![krilnon](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/krilnon/32/34_2.png) [@krilnon](https://forum.kirupa.com/u/krilnon)\
**Post date:** [May 16, 2015, 9:39pm UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196/2 "2015-05-16T21:39:33Z")

</div>

LGTM. I didn’t remember mergesort offhand, but looking at your code I remember the approach.

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [May 17, 2015, 3:45am UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196/3 "2015-05-17T03:45:28Z")

</div>

I’m slowly making progress on a small book on sorting algorithms, and that’s my interest in this particular one at this time. Otherwise, I would just call a `sort` method on the Array and call it good 😛

---

<div class="post-metadata">

**Author:** ![krilnon](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/krilnon/32/34_2.png) [@krilnon](https://forum.kirupa.com/u/krilnon)\
**Post date:** [May 17, 2015, 4:05am UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196/4 "2015-05-17T04:05:47Z")

</div>

If you’re going to put this on ink, you should sort out some small semicolon issues. You have one at the end of the `merge` declaration (but not after `mergeSort`, so something’s inconsistent). Then you don’t have one at the end of `var example`.

> [@kirupa](#):
>
> Otherwise, I would just call a sort method on the Array and call it good

Yeah, I don’t think anyone here doubts that you know the appropriate times and places to roll your own sorts. :kommie:

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [May 17, 2015, 4:58am UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196/5 "2015-05-17T04:58:50Z")

</div>

Ah, good catch on the semicolon issue! I removed it after the merge declaration and added it to example. JSLint pointed it to me as well, but I forgot to update it haha.

---

<div class="post-metadata">

**Author:** ![alltom](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/alltom/32/7274_2.png) [@alltom](https://forum.kirupa.com/u/alltom)\
**Post date:** [May 18, 2015, 4:01am UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196/6 "2015-05-18T04:01:06Z")

</div>

Are you teaching algorithms or JavaScript (or both)? The way you implement the “add the remaining items to the result” section suggests a nice mental image for how merge sort works algorithmically, but realistically, to add a bunch of items to the end of an array in JavaScript, you’d probably use `result.push.apply(result, left)`.

---

<div class="post-metadata">

**Author:** ![kirupa](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/kirupa/32/11616_2.png) [@kirupa](https://forum.kirupa.com/u/kirupa)\
**Post date:** [May 21, 2015, 12:33am UTC](https://forum.kirupa.com/t/mergesort-in-javascript/633196/7 "2015-05-21T00:33:05Z")

</div>

90% teaching with 10% being a nod to an example implementation in JavaScript. You can see an example of what a chapter might look like here: [http://www.kirupa.com/sorts/quicksort.htm](http://www.kirupa.com/sorts/quicksort.htm)

Regarding your feedback on optimizing the code further, you are right - there is a balance to strike between a nice mental image and how to implement them in real life. Since I am skewing this heavily towards beginners, my current thinking is to optimize for the “mental image” side of things.