# I wrote merge sort in Ruby

I am learning sorting algorithms these days. And to me merge sort looks simple than other sorts. (There are merge sort, insertion sort, quick sort, selection sort, bubble sort, et cetera.)

I thought I should try to write it in Ruby.

The steps of the merge sort are:

• First, split the array (yes, I’m sorting an array of numbers) into two halves.
• Second, sort those two arrays.
• And then, merge the two sorted arrays and update original array, in the order of “small number first”. (yes, I’m sorting it in ascending order)

As always, I am writing a test first (lol) because I like to see some tests are passing.

``````class Sorter
def self.merge_sort(array)
array.sort # make the test pass
end
end

require "minitest/autorun"

class SorterTest < Minitest::Test
def test_merge_sort
array = [2, 1, 3]
assert_equal [1, 2, 3], Sorter.merge_sort(array)
end
end
``````

I am going to name the two sorted arrays as `left` and `right`

``````class Sorter
def self.merge_sort(array)
left = array[0..mid]
right = array[mid + 1..-1]
# not done yet
end
end
``````

What is `mid`? It is index of an element which is in the middle. In my case, I include this element to the `left` array.

``````class Sorter
def self.merge_sort(array)
mid = (array.size - 1) / 2
# when array has 3 elements, mid index is 1
left = array[0..mid]
# then this one becomes array[0..1] (2 elements)
right = array[mid + 1..-1]
# this one becomes array[2..-1] (1 element)
# ...
end
end
``````

Let’s not forget these two arrays (`left` and `right`) are magically sorted. And do not worry because there will be magical “recursion”.

And then, pick the smallest number from the two arrays. Here, we already know the smallest number of each array. (duh, they are sorted)

Now I can compare the leftmost element of `left` array and the leftmost element of `right` array, and update original array with smaller one, one by one.

``````class Sorter
def self.merge_sort(array)
mid = (array.size - 1) / 2
left = array[0..mid].sort
right = array[mid + 1..-1].sort
array.size.times do |i|
if left < right
array[i] = left.shift
else
array[i] = right.shift
end
end
array
end
end

require "minitest/autorun"

class SorterTest < Minitest::Test
def test_merge_sort
array = [2, 1, 3]
assert_equal [1, 2, 3], Sorter.merge_sort(array)
end
end
``````

Yay! the test fails with error because there are edge cases! It is because one out of two arrays didn’t have the leftmost element at some point. (in other words, the array was empty)

For example, `left` can be `nil` when `right` is an integer.

``````ArgumentError: comparison of Integer with nil failed
``````

This time I change the conditions and loops, to see how things are going.

``````class Sorter
def self.merge_sort(array)
mid = (array.size - 1) / 2
left = array[0..mid].sort
right = array[mid + 1..-1].sort
i = 0
while left.size > 0 && right.size > 0
if left < right
array[i] = left.shift
i += 1
else
array[i] = right.shift
i += 1
end
end
while left.size > 0
array[i] = left.shift
i += 1
end
while right.size > 0
array[i] = right.shift
i += 1
end
array
end
end
``````

Now test shall pass! By the way, I am not supposed to use `sort` method in the `merge_sort` method to be honest. So let’s now use recursion and complete the code. But look, don’t forget the base condition.

``````class Sorter
def self.merge_sort(array)
return array if array.size == 1

mid = (array.size - 1) / 2
left = merge_sort(array[0..mid])
right = merge_sort(array[mid + 1..-1])
i = 0
while left.size > 0 && right.size > 0
if left < right
array[i] = left.shift
i += 1
else
array[i] = right.shift
i += 1
end
end
while left.size > 0
array[i] = left.shift
i += 1
end
while right.size > 0
array[i] = right.shift
i += 1
end
array
end
end
``````

Cool!