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

Answer 2

write this

 return lists if lists.count == 1

instead of

 lists if lists.count == 1

In Ruby, from a method last statement is always returned by default. But if you want to return from the middle of any lines except the last line conditionally, you must need to use return keyword explicitly.