如何编写合并排序? [英] How do I write a merge sort?

问题描述

我正在尝试实现合并排序，并且在运行代码时遇到stack level too deep (SystemStackError)错误.我不确定是什么问题.

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]

任何帮助都会很棒！

推荐答案

来自 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

这篇关于如何编写合并排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！