Mergesort in JavaScript

programming web dev
1

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 :stuck_out_tongue:

Cheers,
Kirupa

2

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

3

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 :stuck_out_tongue:

4

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.

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

5

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.

6

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

1 Like
7

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

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.