The Rambling Programmer

Merge Sort

Data Structures & Algorithms

If you aren’t familiar with recursion please read last weeks post, Recursion, A Prelude to Merge Sort. Done? Good, let’s jump right into things then. As promised this week we will have a go at implementing a merge sort algorithm in Ruby. This is going to test our understanding of the stuff we learned in last week’s recursion post.

The merge sort is a textbook example of a divide-and-conquer algorithm. The idea being that we “divide” the array to be sorted into two sub-arrays of half the size. Then “conquer” the problem by sorting the two sub-arrays recursively using the merge sort algorithm. Finally we combine the two sorted sub-arrays back together, producing the sorted solution. This may sound a little confusing, but it will make more sense as we move along.

The below image will hopefully clear up some confusion.

At the top of the image, we have an unsorted array. We work our way down to single element arrays by recursively calling our merge sort function. The base case, remember every recursive algorithm must have a base case, is when we reach single element arrays. Then we can start comparing elements and merging them back together. Lets take a look at the code.

def merge_sort(arr)
  if arr.length <= 1  # Base Case
    return arr
  end

  mid_pt = arr.length / 2   # Divide
  left_arr = merge_sort(arr[0, mid_pt])
  right_arr = merge_sort(arr[mid_pt, arr.length])

  sorted_arr = merge(left_arr, right_arr)  # Conquer
end

Notice, the base case, arr of size 1. Also notice the two clear steps. First, “divide” if we are not at length of 1, split the array and recursively call merge_sort again with the two new arrays. Then “conquer” by merging back together. We haven’t written the merge algorithm yet, but don’t worry, we will.

So how do we implement the merge algorithm? Its fairly straightforward, but lets step through it. By the time we first call our merge function we are down to arrays of size 1, this simplifies the work we do significantly, and also helps us wrap our heads around the algorithm a little bit easier. At this point we simply compare our two single element arrays and push them onto the sorted array in the appropriate order. Easy, right?

What little complexity that exists in the merge algorithm comes about when we start considering arrays of size larger than one. This is not terribly difficult either though. We simply repeat the above steps until either the left sub-array or the right sub-array is empty, then push whatever elements are left over onto the end of the sorted array. Lets see this in action below.

def merge(left_arr, right_arr)
  sorted = []

  until left_arr.empty? || right_arr.empty?
    if left_arr[0] <= right_arr[0]
      sorted << left_arr.shift
    else
      sorted << right_arr.shift
    end
  end

  sorted.concat(left_arr).concat(right_arr)
end

Pretty cool! We create an empty array to eventually return. Then we push elements onto that array in order until one of the two input arrays is empty. Finally we just concatenate whatever is left onto the sorted array and implicitly return it. That last line might be a little odd looking, we could rearrange it and concatenate the right array then the left array, it would make no difference, since one of the two arrays has to be empty anyway.

There you have it, a ruby implemented version of merge sort. Without diving too deep into the math lets talk about the complexity of the algorithm. Most divide-and-conquer algorithms will have a complexity of some sort of log n, there are exceptions to this rule, just like with most rules. With the merge sort we get an O(n log n). Basically the division of the arrays is an O(n) operation, and the merging of the arrays back to a final solution is an O(log n) operation. Resulting in an O(n log n) worst case. I know that is not a very satisfying analysis but the math involved in a true analysis of this algorithm is beyond the scope of this article.

Thanks for reading, below are a few links if you would like some supplemental material to study regarding the merge sort.

Merge Sort

This really helped me understand Merge Sort better. Thanks!

Posted by Layne over 7 years ago

Sorting is cool!

Posted by James over 6 years ago