Overflow error on mergesort of linked list

Question

so I was finally able to get the test function to work but I am not passing the test function on this mergesort of linked list. After hours of debugging now it gets worst with the following overflow error.

Unhandled exception at 0x01041719 in ConsoleApplication2.exe: 0xC00000FD: Stack overflow (parameters: 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;
}

The test function was provided in C format but it was working before in c++ too. — user6820297, Sep 15 '16 at 05:44
It probably is a stack overflow. Is your compiler's stack size large enough to handle 500,000 recursions into `merge`? Probably not, if you are using Visual Studio (which defaults to 1MB). — The Dark, Sep 15 '16 at 06:16
@user6820297 The right tool to solve such problems is your debugger. You should step through your code line-by-line *before* asking on Stack Overflow. For more help, please read [How to debug small programs (by Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). At a minimum, you should \[edit] your question to include a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example that reproduces your problem, along with the observations you made in the debugger. — πάντα ῥεῖ, Sep 15 '16 at 06:38
@user6820297 You should be fine once you change your merge to be iterative rather than recursive which uses `O(n)` stack frames (recursive calls), sort is fine because it only makes `O(log(n))` recursive calls. — Timothy Murphy, Sep 15 '16 at 13:55

score 0 · Accepted Answer · edited May 23 '17 at 12:01

This is because of too many recursive calls (in this case: 500 000). Reduce the list size if possible (which rarely happen) or find a way to replace the recursion with iteration. You can use your own stack structure to store the pointers and use a loop instead of recursively call the function.

Assume that the pointer size is 4 bytes, with 3 pointers in the function and the EIP, at the last recursive call, the memory consumed would be 500 000 * 4 * 4 (more than 7.5MB). Is your program's stack size larger than 7.5MB?

By the way, considering making 500000 a constant, avoid using magic number.

Overflow error on mergesort of linked list

1 Answers1