Iterative Ruby Merge Sort

merge_sort.rb

module MergeSort
  def self.sort(list)
    list = list.map{|i| [i]}
    list = pairs list while list.size > 1
    list.flatten
  end

  def self.pairs(list)
    return list if list.size < 2

    x, y, *xs = list

    [self.merge(x,y)] + self.pairs(xs)
  end

  def self.merge(xs, ys)
    return ys if xs.empty?
    return xs if ys.empty?

    x, *xs_ = xs
    y, *ys_ = ys

    if x < y
      [x] + merge(xs_, ys)
    else
      [y] + merge(ys_, xs)
    end
  end
end

merge_sort_spec.rb

require 'rspec'
require_relative 'merge_sort'

describe MergeSort, '.sort' do
  it "sorts shit" do
    examples = [
      [],
      [1],
      [2,1],
      [6,2,3,1,7]
    ]

    examples.each do |example|
      MergeSort.sort(example).should == example.sort
    end
  end
end

Cool. Now switch to tail-recursive and turn on tail-call optimization. :)

The iterative version is slower in Ruby than the recursive version right out of the gate. It's just interesting from a stylistic point of view.

For reference, here's the recursive version:

def self.recursive_sort(list)
  size = list.size
  return list if size < 2
  mid = size/2

  left, right = list[0,mid], list[mid, size]

  merge recursive_sort(left), recursive_sort(right)
end