12 July 2013

merge sort

by mo

This is another divide and conquer sorting algorithm.

  • worst case: O(n log n)


  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.


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))


  def merge(left, right)
    result = []
    result << ((left.first <=> right.first) == -1 ? left.shift : right.shift) until left.empty? || right.empty?
    result + left + right
algorithms 💎