Ошибка переполнения для mergesort связанного списка

Question

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

Необработанное исключение в 0x01041719 в ConsoleApplication2.exe: 0xC00000FD: переполнение стека (параметры: 0x00000001, 0x006E2FC0).

#include <stdio.h> 
#include <stdlib.h> 

struct listnode {struct listnode * next; int key; }; 

struct listnode * merge(struct listnode * left, struct listnode * right) 
{ 
    struct listnode * right2; 

    if (left == NULL) 
     return right; 

    if (right == NULL) 
     return left; 

    if (left->key < right->key) 
    { 
     right2 = left; 
     right2->next = merge(left->next, right); 
    } 
    else 
    { 
     right2 = right; 
     right2->next = merge(left, right->next); 
    } 

    return right2; 
} 

struct listnode *sort(struct listnode * a) 
{ 
    struct listnode * left, * right; 

    if (a== NULL || a->next == NULL) 
     return a; 

    left = a; right = a->next; 

    while (right!= NULL && right->next != NULL) 
    { 
     left = left->next; 
     right = right->next->next; 
    } 

    right = left->next; 
    left->next = NULL; 

    return merge(sort(a), sort(right)); 
} 


int main() 
{ 
    long i; 
    struct listnode *node, *tmpnode, *space; 
    space = (struct listnode *) malloc(500000 * sizeof(struct listnode)); 
    for (i = 0; i < 500000; i++) 
    { 
     (space + i)->key = 2 * ((17 * i) % 500000); 
     (space + i)->next = space + (i + 1); 
    } 
    (space + 499999)->next = NULL; 
    node = space; 
    printf("\n prepared list, now starting sort\n"); 
    node = sort(node); 
    printf("\n checking sorted list\n"); 
    for (i = 0; i < 500000; i++) 
    { 
     if (node == NULL) 
     { 
      printf("List ended early\n"); 

     } 
     if (node->key != 2 * i) 
     { 
      printf("Node contains wrong value\n"); 

     } 
     node = node->next; 
    } 
    printf("Sort successful\n"); 
    return 0; 
} 

Answer 1

Это связано с слишком большим количеством рекурсивных вызовов (в данном случае: 500 000). Уменьшите размер списка, если это возможно (что редко бывает) или найдите способ замены рекурсии на итерацию. Вы можете использовать свою собственную структуру стека для хранения указателей и использовать цикл вместо рекурсивного вызова функции.

Предположим, что размер указателя составляет 4 байта, с 3 указателями в функции и EIP, при последнем рекурсивном вызове потребляемая память будет 500 000 * 4 * 4 (более 7,5 МБ). Размер стека вашей программы превышает 7,5 МБ?

Кстати, учитывая, что 500000 постоянных, avoid using magic number.