Слияние Сортировка путаницы, уровень стека слишком глубокий? - PullRequest
Новая
       6

Слияние Сортировка путаницы, уровень стека слишком глубокий?

0 голосов
/ 08 мая 2018

Итак, я изучаю сортировку слиянием (в Ruby), и я в основном понимаю, как она работает, поэтому я просто пишу начало функциональности «mergeSort» и разбиваю массивы: 

array = [5,1,8,3,4,6,11,2]

def mergeSort(arr,beginIndex,endIndex)
  if endIndex > beginIndex
    mid = (beginIndex+endIndex)/2 
    puts mid
    puts "#{arr[0..mid]}"
    puts "#{arr[mid+1..-1]}"
    mergeSort(arr,0,mid) #comment out here?
    mergeSort(arr,mid+1,arr.length-1) #or here?

  end


end
mergeSort(array,0,array.length-1)

Так что я понимаю, что происходит, и что распечатка работает правильно. Однако странная вещь ... если я закомментирую один из вторичных вложенных mergeSort (где я говорю "#comment здесь? Или здесь?), Я получу распечатку, как я думаю. Однако если я уйду и то и другое будет продолжаться вечно, пока я не получу «слишком большой уровень стека». Это странно, потому что закомментировав любой из них, он остановится, когда массив будет иметь длину 1

.

Почему это происходит?

1 Ответ

0 голосов
/ 08 мая 2018

Второй вызов должен быть mergeSort(arr,mid+1,endIndex).

Это прекрасно работает, если вы пропустите второй вызов, потому что вы сужаетесь к началу. Это прекрасно работает, если вы пропустите первый вызов, потому что вы сужаетесь до конца. Сбой, если у вас есть оба, потому что вы идете сортировать первую половину и обнаруживаете себя во втором вызове, все еще пытаясь отсортировать весь массив ... рекурсивно.

...