Как я могу дополнительно закодировать мой метод merged_sort в ruby?

Question

Так что это действительно сложно, так как он использует рекурсию, и я не могу go дальше этого. Я не знаю, что делать дальше. для описания, 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 

Answer 1

Сортировка слиянием имеет две фазы: (1) разделить и (2) победить / объединить. Фаза разделения разделяет массив на левую и правую половины. Фаза слияния объединяет результаты. Ваша функция merge_sort () должна вызываться рекурсивно в левой половине и правой половине, каждая из которых возвращает отсортированный подмассив. Затем для объединения двух подмассивов должна быть вызвана функция слияния.

По сути, когда вы хотите отсортировать массив, рекурсивная функция делит массив пополам во время рекурсии, а затем объединяет отсортированные половины по мере раскручивания рекурсии, что-то вроде это,

# 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