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!

No correct solution

OTHER TIPS

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

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.

A simplified version with comments

def merge_sort(arr)
  # 0. Base case
  return arr if arr.length <= 1

  # 1. Divide
  mid = arr.length / 2
  arr0 = merge_sort(arr[0, mid])
  arr1 = merge_sort(arr[mid, arr.length])

  # 2. Conquer
  output = merge(arr0, arr1)
end

def merge(l, r)
  output = []
  until l.empty? || r.empty?
    output << if l.first <= r.first
                l.shift
              else
                r.shift
              end
  end
  # The order of `concat(l)` or `concat(r)` does not matters
  output.concat(l).concat(r)
end

https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms

This is a good way to do it. Tis a bit tricky at first, but stay at it.

def merge_sort list
  if list.length <= 1
    list
  else
    mid = (list.length / 2).floor
    left = merge_sort(list[0..mid - 1])
    right = merge_sort(list[mid..list.length])
    merge(left, right)
  end 
end 

def merge(left, right)
  if left.empty?
    right
  elsif right.empty?
    left
  elsif left.first < right.first
    [left.first] + merge(left[1..left.length], right)
  else
    [right.first] + merge(left, right[1..right.length])
  end
end 
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top