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