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[0] < right[0]
        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[0] can be nil when right[0] 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[0] < right[0]
        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[0] < right[0]
        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!