Merge Sort on singly linked list

Question

I have a problem with my mergesort code in C++. I dont know why, but these functions doesn't work propertly, when I'm calling them from Merge_Sort. Separately they works.

When I enter such a list: H->1->2->8->4->7->6->33->NULL

As a sorted list I get something like this: H->33->4->6->NULL.

void Split(node *&H, node *&h1, node *&h2)
{
    if (H != NULL)
    {
        node *P = H;
        bool check = 0;
        while (H != NULL)
        {
            P = H;
            H = H->next;
            if (check) {
                AddLastNode(h2,P);
            }
            else
            {
                AddLastNode(h1, P);
            }
            check=!check;
        }
    }
}

void Merge(node *&H, node *&h1, node *&h2)
{
    node *p1=h1, *p2=h2;
    node *temp = H;
    while (h1!=NULL && h2!=NULL)
    {       
        p1 = h1;
        p2 = h2;
        if (p1->val < p2->val)
        {
            h1 = h1->next;
            temp = p1;  
        }
        else
        {
            h2 = h2->next;
            temp = p2;
        }
        temp->next = H;
        H = temp;
    }
    if (h1 == NULL)
    {
        temp = h2;
        temp->next = H;
        H = temp;
    }
    else if (h2 == NULL)
    {
        temp = h1;
        temp->next = H;
        H = temp;
    }
}

void Merge_Sort(node *&H)
{
    node *h1, *h2;
    if (H && H->next)
    {
        h1 = h2 = NULL;
        Split(H, h1, h2);
        Merge_Sort(h1);
        Merge_Sort(h2);
        Merge(H, h1, h2);
    }
}

Answer 1

Problem is in recursive call Merge_Sort. You call it with reference on pointer so at the end they became with 1 length and other data is lost. I think it is bad algorithm. You can do it more easily with STL containers and algorithms. Use std::list as container, separate it. Then use list method sort on separated containers and make merge on new container or one of h1,h2. Here is my code for your merge algorithm:

#include <iostream>
#include <string>
#include <algorithm>
#include <list>

void TraceList( const std::list<int32_t>& lst, const std::string& title = "" )
{
    if ( !title.empty() )
    {
        std::cout << title << std::endl;
    }
    std::copy(lst.begin(), lst.end(), std::ostream_iterator<int16_t>(std::cout, ","));
    std::cout << std::endl;
}

int main()
{
    //Input test data. You can use here your input code
    const uint32_t SIZE_START = 10;
    int16_t ArrInputData[SIZE_START] = {4, 45, 12, 78, 11, 17, 2, 58, 79, 10 };
    std::list<int32_t> StartList;
    std::copy(ArrInputData, ArrInputData + SIZE_START, std::back_inserter(StartList));

    //Separate input data on parts
    std::list<int> h1;
    std::list<int> h2;
    bool CounterFlag = true;
    std::for_each(StartList.begin(), StartList.end(), [&CounterFlag, &h1, &h2]( int16_t val )
                  {
                      CounterFlag ? h1.push_back(val) : h2.push_back(val);
                      CounterFlag = !CounterFlag;
                  });

    //Sort separated parts
    h1.sort();
    h2.sort();
    TraceList(h1, "H1 list:");
    TraceList(h2, "H2 list:");

    //Merge separated
    std::list<int32_t> FinalMergedList = h1; //Copy one of separated to new list
    FinalMergedList.merge(h2);
    TraceList(FinalMergedList, "MergeFinal list:");

    return 0;
}

Result is:

H1 list:
2,4,11,12,79,
H2 list:
10,17,45,58,78,
MergeFinal list:
2,4,10,11,12,17,45,58,78,79,
Program ended with exit code: 0

If you like my solution with std::list then also you should think about other container. std::list is good when you insert between tail and head, but it is bad at sort. May be you should use any containers with random access, they are faster at sort, for example std::vector.