This is another divide and conquer sorting algorithm.

steps

  1. dive the unsorted list into sublists, until each list contains a single item.
  2. repeatedly merge the sublists until there is a single list.

The sorting takes place during the merge step.

example

In this example, the two lists are split in half. Then recursively, split in half repeatedly until the base case. The base case is when the sub list has 0 or 1 items in the list.

Once the base case is reached, the sublists are merged and sorted until there is a single sorted list. The <=> is the ruby comparison operator, which is similar to c# IComparable interface, or java’s Comparable interface.

class MergeSort
  def sort(items)
    return items if items.size <= 1
    pivot = items.size/2
    left, right = items[0...pivot], items[pivot...items.size]
    merge(sort(left), sort(right))
  end

  private

  def merge(left, right)
    result = []
    result << ((left.first <=> right.first) == -1 ? left.shift : right.shift) until left.empty? || right.empty?
    result + left + right
  end
end
comments powered by Disqus