Implement Merge Sort in JavaScript
Michael Mitrakos
4 min read
Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…
Implement Merge Sort in JavaScript
Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!
JavaScript eBook
I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!
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.
When Merge Sort in JavaScript is Useful
Merge Sort is a highly useful sorting algorithm in JavaScript when there is a need for efficient sorting of large data sets. This algorithm operates on the principle of dividing the array into smaller subarrays, sorting them individually, and then merging them back into a sorted sequence. With its time complexity of O(n log n), Merge Sort guarantees stable and reliable sorting performance. Its recursive nature allows for easy parallelization, making it suitable for optimizing sorting tasks in multi-threaded or distributed environments. By leveraging the power of Merge Sort, JavaScript developers can efficiently handle sorting operations on extensive data, ensuring faster and more responsive applications.
Simplified Pseudocode
Recursively divide list into *n lists *Call merge on each sublist then until combined into one list
Detailed Pseudocode
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
```javascript
}
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
Thanks for joining along on learning merge sort! This one was fun. Ready to get even more advanced? Hop on over to [bucket sort](https://initjs.org/bucket-sort-in-javascript-dc040b8f0058#.5j5ls9und)!
#### JavaScript eBook
I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. [Check out the ebook now](https://www.mitrakos.com/ebook)!
I founded [Higglo Digital](https://higglo.io) and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a *beautifully designed website*, [check us out](https://higglo.io).
I also created [Wanderlust Extension](http://www.wanderlustapp.io/) to discover the most beautiful places across the world with highly curated content. Check it out!