In this lesson on sorting algorithms, we are going to implement the merge sort algorithm. Though merge sort is a popular sorting method, it's not used as much as quick sort because it is slightly slower in real world scenarios. However I love merge sort because it is easy to understand from a high-level perspective. In terms of coding, it has a slightly longer code implementation than quicksort, but is also easier to understand.

At a high level merge sort breaks down the entire array into smaller groups, sorts the values inside each subgroup and merges it with the larger group to sort a collection.

To implement the algorithm we are going to create two methods, one called merge and the other called merge_sort.

def merge_sort(list)
end

def merge(left, right)
end

As the name suggests, merge will take the right and left values and will merge them together. We will begin by writing the code inside our merge method.

def merge(left, right)
  if left.empty?
    right
  elsif right.empty?
    left
  elsif left.first < right.first
    [left.first] + merge(left[1..left.length], right)
  else
    [right.first] + merge(left, right[1..right.length])
  end
end

In this merge method, we start with a conditional that returns the right value if the left value is empty and left if the right is empty. This makes our validation much easier. If both these conditions are not true, then we are going to check if the first value in the left side is less than the first value on the right side. If so, we are going to recursively call merge to bring the arrays together.

Next we'll implement the merge_sort method.

If the length of the array is one item or less, then simply return the array as it requires no sorting. If there are more than two elements in the array we are dividing the array into two halves. For the left side we are recursively calling the merge_sort method with the parameter being the values from the first to the mid element. For the right side too, we are going to call the merge_sort method recursively, but the parameters will be from the mid value to the end of the list. Finally, we are calling the merge method with left and right arrays as its parameters.

The entire code is:

def merge_sort(list)
  if list.length <= 1
    list
  else
    mid = (list.length / 2).floor
    left = merge_sort(list[0..mid - 1])
    right = merge_sort(list[mid..list.length])
    merge(left, right)
  end
end

Now we can test this out with the following code:

arr = [4, 1, 5, 1, 33, 312]
p merge_sort(arr)

The output for this program is:

[1, 1, 4, 5, 33, 312]

So, that's how you implement merge sort in Ruby.