« back

All Sorts of Things - Merge Sort

22 Oct 2012

You know you can't resist a merge sort folk dance.

Merge sort is another divide and conquer algorithm. It is of O(n log n) complexity. I have really been having fun with sorting algorithms so let's walk through merge sort. The basic idea is this...

1     1. Divide a list into n lists each containing 1 element.
2     2. Repeatedly merge the sublists while ordering them until there is only one list again.
3     

I am going to build this idea out as two methods where one of them calls the other. The first method will be the main merge_sort method, which will break the list into sub lists and ultimately one element arrays. The second method will be called merge and it will do the merging back together of the lists(duh.).Since this algorithm will be recursive, we need to start with a base case to break us out of the recursion when necessary.

1     def merge_sort(array)
2         return array if array.length < 2
3     end
4     

Once we have established our base case, the easiest way to divide the list in half is to find a midpoint, take everything below it and put it in one list, and take it and everything above it and put it in another.

1     def merge_sort(array)
2         return array if array.length < 2
3         midpoint = array.length/2
4         list_1 = array[0..(midpoint - 1)]
5         list_2 = array[midpoint..(array.length - 1)]
6     end
7     

Okay, get ready, now the really cool part starts to happen. Recursion. It almost seems like magic. :)

1     def merge_sort(array)
2         return array if array.length < 2
3         midpoint = array.length/2
4         list_1 = array[0..(midpoint - 1)]
5         list_2 = array[midpoint..(array.length - 1)]
6         new_list_1 = merge_sort(list_1) // calls itself to further divide the list
7         new_list_2 = merge_sort(list_2) // calls itself to further divide the list
8     end
9     

Oh, and don't forget the secret sauce! Now that have broken everything apart, we need to merge these things back together(in the proper order, of course.). Let's anticipate the fact that we are going to create a merge method that will take two arrays.(The one to the left of the midpoint and the one to the right of the midpoint.) For now, in this method, we will need to call our not yet implemented method and pass it our two arrays.

 1     def merge_sort(array)
 2         return array if array.length < 2
 3         midpoint = array.length/2
 4         list_1 = array[0..(midpoint - 1)]
 5         list_2 = array[midpoint..(array.length - 1)]
 6         new_list_1 = merge_sort(list_1) // calls itself to further divide the list
 7         new_list_2 = merge_sort(list_2) // calls itself to further divide the list
 8         new_list = merge(new_list_1, new_list_2) //   <-----------calls the merge method
 9     end
10     

For readability I decided to break the merging part into it's own method. Like I stated above, the merge method is going to take two arrays as arguments. The goal is to put these back together in an ordered fashion, so let's create a merged_list variable that will house the array that we are putting back together.

1     def merge(array_1, array_2)
2       merged_list = []
3     end
4     

We are going to want to keep comparing the values from array_1 with those in array_2. We want the loop to stop when we can not compare them any more. Let's use until. Until either of the arrays are empty, we want to push the lesser value into the merged_list. If we shift the value off when we add it to the new list, it will save us the headache of having to increment a counter and to keep track of where we are at. We will always just compare the first elements.

 1     def merge(array_1, array_2)
 2       merged_list = []
 3       until array_1.empty? || array_2.empty?
 4          if array_1.first <= array_2.first
 5             merged_list << array_1.shift
 6          else
 7             merged_list << array_2.shift
 8          end
 9       end
10     end
11     

When one of the arrays goes empty, we know that either array that is left is already sorted within itself. In, that case, we know they are all values that are larger than what is in the sorted list since we have always been selecting for the smallest value. Then we can add the array with the leftover elements in it to the end of the merged list. Then, TA-DA! The sorted list is complete. "HEY!" "How do you know which array has elements left in it?" Well, that is a very good question and the answer is that with this implementation of merge_sort you don't need to know. "WHAT!?" That's right. By concatenating both the arrays with the merged list regardless of if they are empty of not, you will end up with your desired result. The array that is empty will add nothing to your merged_list and you will only be left with a beautifully sorted list. :D - Ama -zing!

 1     def merge(array_1, array_2)
 2       merged_list = []
 3       until array_1.empty? || array_2.empty?
 4          if array_1.first <= array_2.first
 5             merged_list << array_1.shift
 6          else
 7             merged_list << array_2.shift
 8          end
 9       end
10       merged_list.concat(array_1).concat(array_2)
11     end
12     

comments powered by Disqus