Simple merge_sort on list - analysis

Question

I wrote simple function, that merge two sorted list into one. Unfortunately, I couldn't get a result, I don't know why. Compilator don't show any statements, and stop working while starting the function. It seems me to be ok everything. Check that, please. Below is shown the code.

node list_sort (node*& h, node*& h1, node*& h2)
{
    if (h1 && h2 == NULL)
    {
        h = h1;
        return *h;
    }

    if (h2 && h1 == NULL)
    {
        h = h2;
        return* h;
    }

    if (h1 == NULL && h2== NULL)
    {
        h = NULL;
        return* h;
    }

    if (h1 && h2) // condition required to set a head
    {
        if (h1->vol > h2->vol)
            h = h2;

        else
            h = h1;
    }

    mode* p;
    p = h;

    while (h1 && h2)
    {
        if (h1->vol > h2->vol)
        {
            p->next = h2;
            h2 = h2->next;
        }

        else
        {
            p->next = h1;
            h1 = h1->next;
        }

        p = p->next;
    }

    if (h1)
    {
        while (h1)
        {
            p->next = h1;
            h1 = h1->next;
            p = p->next;
        }
    }

    else
    {
        while (h2)
        {
            p->next = h2;
            h2 = h2->next;
            p = p->next;
        }
    }

    h1 = NULL;
    h2 = NULL;
    return* h;
}

Doesn't compilator object to this? `node list_sort (node*& h, node*& h1, node*& h2)` — Weather Vane, May 18 '15 at 17:49
You use references (`node *&h1`), which are available in C++, but not in C. Dou you want a C or a C++ solution? — M Oehm, May 18 '15 at 18:01
I made some mistakes. I use C++, not C (I used uncorrect tags). Regards node/mode - deal it as the same. Maybe I should use void and do not return any list? @Weather Vane, compilator accept this notation — Plusce, May 18 '15 at 18:08
@Martin: Yes, the function as is should probably be `void`. Alternatively, you could omit the first parameter and return a new list. — M Oehm, May 18 '15 at 18:25
Is it `compilator` or `compiler` ? I'm starting to get very confused. — Samveen, May 28 '15 at 03:40

M Oehm · Accepted Answer · 2015-05-18T18:44:13.897

When you assign the new head, you must also advance the list you take it from:

if (h1 && h2)
{
    if (h1->vol > h2->vol) {
        h = h2;
        h2 = h2->next;
    } else {
        h = h1;
        h1 = h1->next;
    }
}

Otherwise you will take the same node, say h1 again in the while loop, but its next pointer is h1. Ad infinitum ...

The condition if (h1 && h2) ... is also redundant, because you have treated all other cases earlier. (But you should set the source lists to NULL in these cases, too, to maintain the logic of the function: The source lists are used up, all elements are now in the merged list h.)

Note that you don't need the last two while loops: The rest of the list already has the right connections. You just have to set:

p->next = (h1 != NULL) ? h1 : h2;
h1 = NULL;
h2 = NULL;

The semantics of your function are also unusual. If you pass the merged list head as reference, you don't have to return a node. You could return the new head, but that would be redundant. You could return some related information, say the count of the merged list, which the caller is free to ignore. Or just make the function void.

You could return the new list head and leave out the first parameter:

node *list_merge(node *&h1, node *&h2)
{
    node *h = NULL;

    // merge list

    return h;
}

Finally, you can catch all special cases plus merge the if and while loops when you build your new list with a pointer to node pointer:

node *list_sort(node *&h1, node *&h2)
{
    node *h = NULL;
    node **p = &h;

    while (h1 && h2) {
        if (h1->vol > h2->vol) {
            *p = h2;
            h2 = h2->next;
        } else {
            *p = h1;
            h1 = h1->next;
        }
        p = &(*p)->next;
    }

    *p = h1 ? h1 : h2;
    h1 = NULL;
    h2 = NULL;

    return h;
}

That's all, and you get the conciseness by using one level of indirection: The pointer to head-pointer fills in the head h on its first assigment and the next members of the new list as you go.

Thank you. The function is working now. I deleted those useless condition too. But where should I attribute a NULL into any cases? It seems me I wrote it everywhere where it is required. — Plusce, May 18 '15 at 18:40
Fo example when `h2` is null, you set `h` to `h1` and return ´h`. But `h1` will still be the original list, whereas in "normal" operation, you end up with the merged list `h` and the source itsts `h1` and `h2` all exhausted, i.e. `NULL`. — M Oehm, May 18 '15 at 18:46
Yes, indeed. thank you man. yet I have a last question: why "nullptr" doesn't work in my compilator? Shall I add any library? I use Codeblocks. — Plusce, May 18 '15 at 18:52
`nullptr` is a language keyword, whereas `NULL` is a macro from the standard library, for which you need to include the right headers. The `nullptr` represents a null pointer and has been added to C++11, so you need a compiler that implements this standard. Perhaps [this question](http://stackoverflow.com/questions/18174988/how-can-i-add-c11-support-to-codeblocks-compiler) can help you. — M Oehm, May 18 '15 at 19:23

Simple merge_sort on list - analysis

1 Answers1