How do I write a merge sort?

Question

I am trying to implement a merge sort and am getting stack level too deep (SystemStackError) error when I run my code. I am not sure what the issue may be.

def merge_sort(lists)
  lists if lists.count == 1

  middle  = lists[0..(lists.count / 2) - 1 ]
  left = lists[0..middle.count - 1]
  right = lists[middle.count..lists.count]

  x = merge_sort(left)
  y = merge_sort(right)
end

merge_sort [1,2,3,4,5,6,7,8]

Any help would be great!

Answer 1

From wikipedia:

def mergesort(list)
  return list if list.size <= 1
  mid   = list.size / 2
  left  = list[0...mid]
  right = list[mid...list.size]
  merge(mergesort(left), mergesort(right))
end

def merge(left, right)
  sorted = []
  until left.empty? || right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift
    end
  end
  sorted.concat(left).concat(right)
end