MergeSort Example in Ruby

merge_sort.rb

class MergeSortAlgorithm
  # Break's the array down into two numbers (number A and number B) and sorts them.
  def sort(numbers)
    if numbers.size <= 1
      return numbers
    end

    array_size   = numbers.size
    half_of_size = (array_size / 2).round

    left_array  = numbers.take(half_of_size)
    right_array = numbers.drop(half_of_size)

    sorted_left_array = sort(left_array)
    sorted_right_array = sort(right_array)

    merge(sorted_left_array, sorted_right_array)
  end

  # This then creates a new array, loops through the left/right arrays and places the lowest number into the array. 
  def merge(left_array, right_array)
    if right_array.empty?
      return left_array # We have nothing to compare. Left wins.
    end

    if left_array.empty?
      return right_array # We have nothing to compare. Right wins.
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    # We keep doing it until the left or right array is empty.
    recursive = merge(left_array, right_array)

    # Okay, either left or right array are empty at this point. So we have a result.
    [smallest_number].concat(recursive)
  end
end

# Let's give this a spin?
merge_sort = MergeSortAlgorithm.new
puts merge_sort.sort([4, 92, 1, 39, 19, 93, 49, 10].shuffle) # => [1, 4, 10, 19, 39, 49, 92, 93]

# How it works
# 1. Let's say the input is [4, 92, 1, 39, 19, 93, 49, 10]
# 2. Break them down in halfs. So we now have [4, 92, 1, 39] and [19, 93, 49, 10]
# 3. Break them again in halfs. Let's start with the first. So now we have [4, 92] and [1, 39]
# 4. Break until there's only one item in each. So now we have [4] and [92]
# 5. Check which one is lower. So in this case, we know 4 is lower than 92. Let's rearrange it if necessary.
# 6. Now we have [4, 92] and we do the same for [1, 39]
# 7. We now create a new array. []
# 8. We check the first element on the left array versus the first element on the right array (i.e. 4 >= 9) and then add them to the new array.
# 9. Keep doing that until it's done.

MergeSort.markdown

MergeSort Algorithm in Ruby

When learning about sorting algorithms, I wanted to implement them to help me understand them better. This algorithm was originally invented by John von Neumann in 1948.

The Ruby script attached explains in real code what is going on. Play about with it.

How does the algorithm work?

Step by step:

• Pass through an array of unsorted numbers (i.e. [4, 3, 2, 10])
• Algorithm splits the array in half (left = [4, 3] and right = [2, 10])
• Continue to split until only two numbers (we'll call this the two_item_array)
• Find the lowest number in two_item_array (we'll call this smallest)
• The two_item_array is sorted. Return it to parent.
• Parent loops together all instances of two_item_array and compares the first number in all of them, and sorts them accordingly
• Once looped, join all two_item_array items all together
• All sorted!

The core purpose of the algorithm is split it until there is only two items. Once there is two items, you can compare the highest/lowest. There is now many instances of arrays with two items (which they are sorted). We begin to merge arrays based on the first number of every two item array (which are already sorted at this point). These blocks become four item arrays, eight item arrays, etc until the array is back to a complete array (except it is in order!).

This picture visualises the "splitting" process: