Implement Merge Sort in JavaScript

Algorithms
September 30, 2016

This article is part of a series covering sort algorithms in JavaScript. You can find the rest of the series here. If you’re new to sorting algorithms, or algorithms in general, read this first to get a solid foundation for moving forward. Today I’ll be covering the ins and outs of merge sort. This is probably the first useful sorting algorithm I’m covering. Merge sort is a stable sort just like insertion sort. Not sure what a stable sort is? I explain it in my introduction to sort algorithms.

Analysis

So where does the name come from? It’s based on the idea that it’s easier to merge two already sorted lists than it is to sort one unsorted list. Therefore, merge sorts start by creating n number of single item lists (n is the total number of items in the list). Merge sort then starts to combine these single item lists into a single sorted list.

Complexity

The time complexity of this algorithm, at worst case, is linearithmic — O(log n!). This is one of the more efficient sorting algorithms, which is why most browsers use merge sort as the built in Array.sort method.

One thing to note about merge sort is that it’s not ‘in place’. During merging, it creates a copy of the entire array being sorted, which means it copes more than a constant number of elements at some time. Due to this, the space complexity of this algorithm is actually greater than most, and are not commonly used in larger systems where space is at a premium. Some in place sorts include selection sort and insertion sort.

Simplified Pseudocode

Recursively divide list into n lists Call merge on each sublist then until combined into one list

Detailed Pseudocode

function mergeSort(array) { If array length < 2 Return array Create var for middle index of array Create var for far left index of array Create var for far right index of array Recursively call mergeSort function } Function merge (node1, node2) { Create var for result array While node1 length > 0 and node2 length > 0 If node1[0] < node2[0] Shift node1 and push to result array else Shift node2 and push to result array Return concat node1 or node2 (depending if node1 is empty or not)

Code

function mergeSort (arr) { if (arr.length < 2) { return arr; } var mid = Math.floor(arr.length / 2); var subLeft = mergeSort(arr.slice(0, mid)); var subRight = mergeSort(arr.slice(mid)); return merge(subLeft, subRight); } function merge (node1, node2) { var result = []; while (node1.length > 0 && node2.length > 0) result.push(node1[0] < node2[0]? node1.shift() : node2.shift()); return result.concat(node1.length? node1 : node2); }

Thanks for joining along on learning merge sort! This one was fun. Ready to get even more advanced? Hop on over to bucket sort!

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

More Blog Posts