合并排序有两个阶段，(1(除法和(2(征服/合并。除法阶段将数组分成左半部分和右半部分。合并阶段合并结果。需要在左半部分和右半部分递归调用merge_sort((函数，每个函数都返回一个排序的子数组。然后需要调用merge函数来合并这两个子数组。
所以这个非常难，因为它使用递归，我再也不能做得更远了。我不知道下一步该做什么。为了便于描述，merge_sort将数组划分为单个元素，然后我不知道下一步该怎么办，这真的很难，我从 8小时以来就一直在思考这个问题
def merge_sort ( array )
return if array.length < 2
a = merge_sort(array.slice!(0..array.length/2))
b = merge_sort(array)
end
def merge ( a , b )
merged = []
j_a = 0 # pointer to the first list
k_b = 0 # pointer to the second list
while j_a < a.length || k_b < b.length
if a[j_a] > b[k_b]
merged << b[k_b]
k_b += 1
else
merged << a[j_a]
j_a += 1
end
if j_a == a.length # pointer has reached the end of first list? append the whole of 2nd `list`
merged << b[k_b..-1]
else
merged << a[j_a..-1] # else append the first list to merged.
end
end
merged
end
基本上，当你想对数组进行排序时，递归函数会在递归过程中将数组一分为二，然后在递归展开时合并排序后的两半，类似于
# merge sort array charles
def merge_sort ( charles )
return if charles.length < 2
k = charles.length
L = merge_sort(charles[0:k/2])
R = merge_sort(charles[k/2+1:k])
# missing merge
return merge(L,R)
end