Почему переполнение стека происходит при сортировке слиянием? - PullRequest
Новая
       60

Почему переполнение стека происходит при сортировке слиянием?

2 голосов
/ 04 июня 2019

Поэтому, не дождавшись ответа в этой теме , я решил реализовать свою структуру данных.
Проблема, с которой я столкнулся: при сортировке небольших списков все нормально, но при сортировке списка размером 487 элементов в методе merge происходит переполнение стека.

Вот части кода, отвечающие за сортировку.
Есть идеи? 

private function mergeSort($node) {
        if ($node == null || $node->next == null) {
            return $node;
        }

        $second = $this->split($node);

        $node = $this->mergeSort($node);
        $second = $this->mergeSort($second);

        return $this->merge($node, $second);
    }

private function split(Word $word) {
        $fast = $word;
        $slow = $word;
        while ($fast->next !== null && $fast->next->next !== null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
        }
        $temp = $slow->next;
        $slow->next = null;
        return $temp;
    }

private  function merge($first, $second) {
        if ($first === null) {
            return $second;
        }

        if ($second === null) {
            return $first;
        }

        if ($first->begin < $second->begin) {
            $first->next = $this->merge($first->next, $second);
            $first->next->prev = $first;
            $first->prev = null;
            return $first;
        } else {
            $second->next = $this->merge($first, $second->next);
            $second->next->prev = $second;
            $second->prev = null;
            return $second;
        }
    }

Использование: 

//some code here 

$sortedLinedList = $linkedList->mergeSort($linkedList->head);
// stack overflow happens

Обновление: Я обнаружил, что переполнение стека не всегда напрямую зависит от количества элементов в списке. Иногда стек может переполняться 350 элементами, а иногда 487. Возможно, это зависит от данных самого списка. Единственное место, где я непосредственно использую данные узла, - это сравнение в методе merge. Может быть, это происходит потому, что переменная «begin» содержит значение типа float? Я попробовал это: 

round($first->begin, 2) < round($second->begin, 2)

но мне это не помогло: (

...