Merge Sort in Ruby

Overview

Merge is a divide and conquer algorithm for sorting which is generally stable. Its average and worst case performance is O(n log n), which makes it more efficient than Insertion for most sets.

Concise

def merge_sort(a)
  return numbers if numbers.length <= 1
  m = a.length / 2
  p l = a[0...m]
  p r = a[m..a.length-1]
  p l = merge_sort(l)
  p r = merge_sort(r)

  merge(l, r)
end

def merge(l, r)
  o = []
  while l.length > 0 || r.length > 0
    if l.length > 0 && r.length > 0
      l[0] <= r[0] ? o << l.shift : o << r.shift
    elsif l.length > 0
      o << l.shift
    elsif r.length > 0
      o << r.shift
    end
  end
  o
end

a = (0..7).to_a.sort{ rand() - 0.5 }[0..7]
p a

s = merge_sort(a)
p s
merge_sort.rb

Verbose

# Merge Sort
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def merge_sort(numbers)

  # Empty sets and singletons are already sorted.
  if numbers.length <= 1
    return numbers
  end

  # Split array in two.
  middle = numbers.length / 2
  left = numbers[0...middle]
  right = numbers[middle..numbers.length-1]
  puts left.inspect
  puts right.inspect

  # Recursively call merge_sort to divide
  # array into continually smaller sets.
  left = merge_sort(left)
  right = merge_sort(right)
  puts left.inspect
  puts right.inspect

  # Merge sets.
  merge(left, right)
end

def merge(left, right)
  result = []

  # As long as there are elements to compare.
  while left.length > 0 || right.length > 0

    # If there are elements in both sets to compare.
    if left.length > 0 && right.length > 0

      # Smallest element is added to result.
      if left[0] <= right[0]
        result << left.shift
      else
        result << right.shift
      end

    # Otherwise, add remaining elements.
    elsif left.length > 0
      result << left.shift
    elsif right.length > 0
      result << right.shift
    end
  end

  result
end

# Generate array of ten random integers.
unsorted = (0..7).to_a.sort{ rand() - 0.5 }[0..7]
puts unsorted.inspect

# Sort.
sorted = merge_sort(unsorted)
puts sorted.inspect
merge_sort_verbose.rb

Sample Input and Output

$ ruby merge_sort.rb
[5, 6, 7, 1, 4, 3, 2, 0]
[5, 6, 7, 1]
[4, 3, 2, 0]
[5, 6]
[7, 1]
[5]
[6]
[5]
[6]
[5, 6]
[7]
[1]
[7]
[1]
[1, 7]
[1, 5, 6, 7]
[4, 3]
[2, 0]
[4]
[3]
[4]
[3]
[3, 4]
[2]
[0]
[2]
[0]
[0, 2]
[0, 2, 3, 4]
[0, 1, 2, 3, 4, 5, 6, 7]

Further Reading