A Merge of Sorts

Six weeks ago, I graduated from the most intense school experience of my life — a 15-week software engineering bootcamp at the Flatiron School. During my time there, I faced what seemed to be an insurmountable amount of knowledge… until I graduated only to find that the is still an infinite amount of knowledge to be learned. Much of what I have studied since Flatiron involves data structures and algorithms. Among the algorithms I have studied is a group called sorting algorithms, one of which is called Merge Sort — our topic for today.

When I first saw merge sort visualized on Visualgo I thought I was watching true magic happen right before my eyes. It turns out, as long as you have an understanding of the concept of recursion, merge sort is an almost simple idea to understand.

Merge sort is an incredibly popular sorting algorithm. It uses a method call divide and conquer in order to sort an array of elements. Here, that means that we continually break down our original, larger array into smaller arrays until they are of a size that is more manageable. In this case, that size is 0 or 1.

Pseudocode it!

Let’s take a look at our unsorted input array, [37, 27, 43, 2, 9, 82, 10]. It is important to note that we will be sorting this array using JavaScript and outputting a sorted array in ascending order. I mentioned earlier that merge sort uses the divide and conquer method. We will continually cut the array in half until we have all elements of the array in arrays of their own.

Once we have individual elements in individual arrays, we can begin to merge them into new sorted arrays. This process continues until we have merged all sub-arrays back into our final sorted array.

Now code it!

Great! We have a plan of action… Now, let’s code our solution!

The code below is our main function, mergeSort(). It takes in one unsorted array and does the work of dividing it until we have our smallest sub-arrays.

This code is our merge() function. It takes in two sorted arrays as arguments and merges them into one larger array, returning it back to our overarching function.

Time Complexity

The time complexity for merge sort is O(n log n)! Not so bad, eh?