Ошибка рекурсивного слияния Сортировка

Question

Я пишу свою собственную функцию сортировки слияния для собственного класса связанных списков с использованием C++. Я тестировал свои функции Split_List и Merge, и они хорошо работают. Но у меня возникают проблемы с рекурсивной функцией Merge_Sort: она может объединять сортировку левой и правой частей связанного списка, но имеет ошибку при окончательном объединении всего связанного списка.

выход:

первый список: [100] -> [2] -> [37] -> [- 10] -> |||

отсортировано по первому краю: [37] -> [100] -> |||

node.h

#ifndef NODE_H 
#define NODE_H 
#include <iostream> 

template <typename T> 
class node{ 
public: 
    node(const T& data){item=data; link=NULL;} 
    int item; 
    node* link; 
}; 

#endif // NODE_H 

linked_list.h

#ifndef Linked_List_H 
#define Linked_List_H 
#include "node.h" 
#include <iostream> 

using namespace std; 

template<typename T> 
class Linked_List{ 
public: 
    Linked_List(){tail=head=NULL; count=0;} 
    void Insert_Head(const T& item); 
    void Append_Tail(const T& item); 
    void Insertion_Sort(); 
    void Merge_Sort(); 
    void Print(); 
    int Size() {return count;} 
private: 
    node<T>* head; 
    node<T>* tail; 
    int count; 
    void InsertHead(node<T>* &list_head, const T& item); 
    void InsertBefore(node<T>* &list_head, node<T>* here, const T& item); 
    void Append_Tail(node<T>* &list_head, node<T>* end); 
    void Delete(node<T>* &list_head, node<T>* deleteHere); 
    node<T>* DeleteHead(node<T>* &list_head); 
    void Merge_Sort(node<T>* list_head, int size); 
    node<T>* Merge(node<T>* left, node<T>* right); 
    node<T>* Split_List(node<T>* list_head, int size); 
    void Print(node<T>* list_head); 
}; 

template<typename T> 
void Linked_List<T>::Merge_Sort(){ 
    Merge_Sort(head, count); 
} 

template<typename T> 
void Linked_List<T>::Merge_Sort(node<T>* list_head, int size){ 
    int n1; 
    int n2; 
    node<T>* right_head; 

    if(size>1){ 
     right_head=Split_List(list_head, size); 
     n1=size/2; 
     n2=size-n1; 
     Merge_Sort(list_head, n1); 
     Merge_Sort(right_head, n2); 
     head=Merge(list_head, right_head); 
    } 
} 

template<typename T> 
node<T>* Linked_List<T>::Split_List(node<T>* list_head, int size){ 
    if (size==0){ 
     return NULL; 
    }else if (size==1){ 
     return list_head; 
    }else{ 
     node<T>* iter=list_head; 
     node<T>* right_head=NULL; 
     int i=0; 
     while (i<size/2-1){ 
      iter=iter->link; 
      i++; 
     } 
     right_head=iter->link; 
     iter->link=NULL; 
     return right_head; 
    } 
} 

template<typename T> 
node<T>* Linked_List<T>::Merge(node<T>* left, node<T>* right){ 
    node<T>* newHead=NULL; 
    while (left!=NULL && right!=NULL){ 
     if (left->item<=right->item){ 
      Append_Tail(newHead, DeleteHead(left)); 
     }else{ 
      Append_Tail(newHead, DeleteHead(right)); 
     } 
    } 
    if (left==NULL){ 
     while (right!=NULL){ 
      Append_Tail(newHead, DeleteHead(right)); 
     } 
    }else{ 
     while (left!=NULL){ 
      Append_Tail(newHead, DeleteHead(left)); 
     } 
    } 
    return newHead; 
} 


template<typename T> 
void Linked_List<T>::Insertion_Sort(){ 
    node<T>* end=head; 
    while (end!=NULL){ 
     for (node<T>* iter=head; iter!=end; iter=iter->link){ 
      if (iter->item>=end->item){ 
       InsertBefore(head, iter, end->item); 
       Delete(head, end); 
       break; 
      } 
     } 
     end=end->link; 
    } 
} 

template<typename T> 
void Linked_List<T>::Insert_Head(const T& item){ 
    InsertHead(head, item); 
} 

template<typename T> 
void Linked_List<T>::InsertHead(node<T>* &list_head, const T& item){ 
    node<T>* tempPtr=new node<T> (item);  //create new node 
    tempPtr->link=list_head;   //connect the new node to orignal 1st node 
    list_head=tempPtr;    //make the head point to the new node as the new 1st node 
    count++; 
} 

template <typename T> 
void Linked_List<T>::InsertBefore(node<T>* &list_head, node<T>* here, const T& item){ 
    if (list_head==NULL || list_head==here) 
    { 
     InsertHead(head, item);  //add "head" node 
     return; 
    }else{ 
     node<T>* tempPtr=new node<T>(item);  //create new node 

     node<T>* previous=head; 
     while (previous->link!=here){ 
      previous=previous->link;  //if the previous node cannot be found, go to the link node 
     } 
     tempPtr->link=here;     //if the previous node is found, connect the new node to "here" node 
     previous->link=tempPtr; 
     count++; 
    } 
} 

template<typename T> 
void Linked_List<T>::Append_Tail(const T& item){ 
    if (head==NULL) 
    { 
     InsertHead(head, item);  //add "head" node 
     tail=head; 
    }else{ 
     node<T>* tempPtr=new node<T>(item);  //create new node 
     tail->link=tempPtr; 
     tail=tail->link; 
     count++; 
    } 
} 

template<typename T> 
void Linked_List<T>::Append_Tail(node<T>* &list_head, node<T>* end){ 
    if (list_head==NULL) 
    { 
     end->link=list_head;   //connect the new node to orignal 1st node 
     list_head=end;    //make the head point to the new node as the new 1st node 
     count++; 
     tail=list_head; 
    }else{ 
     tail->link=end; 
     tail=tail->link; 
     count++; 
    } 
} 

template<typename T> 
void Linked_List<T>::Delete(node<T>* &list_head, node<T>* deleteHere){ 
    node<T>* here=list_head; 
    if (here==NULL) 
    { 
     cout<<"Empty linked list!";    //empty linked list 
     return; 
    } 
    else{ 
     node<T>* previous=list_head; 
     if (deleteHere==list_head){ 
      list_head=deleteHere->link;    //if the deleted node is the 1st node, let the head point to the link node 
      count--; 
     } 
     else{ 
      while (previous->link!=deleteHere){ 
       previous=previous->link;  //if the previous node cannot be found, go to the link node 
      } 
      previous->link=deleteHere->link; 
      //if the previous node is found, connect the previous node to the node after the deleted node 
      count--; 
     } 
    } 
} 

template<typename T> 
node<T>* Linked_List<T>::DeleteHead(node<T>* &list_head){ 
    node<T>* deleted=list_head; 
    list_head=list_head->link;    //if the deleted node is the 1st node, let the head point to the link node 
    count--; 
    deleted->link=NULL; 
    return deleted; 
} 


template<typename T> 
void Linked_List<T>::Print(){ 
    Print(head); 
} 

template<typename T> 
void Linked_List<T>::Print(node<T>* list_head){ 
    node<T>* iter; 
    for (iter=list_head; iter!=NULL; iter=iter->link){ 
     cout<<"["<<(iter->item)<<"]->"; 
    } 
    cout<<"|||"<<endl<<endl; 
} 

#endif // Linked_List_H 

main.cpp

#include <iostream> 
#include "linked_list.h" 

using namespace std; 

int main() 
{ 
    Linked_List<int> list1; 
    list1.Insert_Head(-10); 
    list1.Insert_Head(37); 
    list1.Insert_Head(2); 
    list1.Insert_Head(100); 
    cout<<"1st list: "<<endl; 
    list1.Print(); 

    cout<<"sorted 1st list: "<<endl; 
    list1.Merge_Sort(); 
    list1.Print(); 
} 

Answer 1

Если добавить некоторые избыточные Print вызовы в вашем коде, вы увидите ваши проблема. Вы правильно сортировать размер-2 списка, но в верхнем уровне одного, после:

Merge_Sort(list_head, n1); 
Merge_Sort(right_head, n2); 

list_head будет список [100]->||| и right_head будет список [37]->|||. Вы на самом деле слияния и правильно сортировки, это просто, что эти указатели не меняются, так что вы начинаете с:

[100] -> [2] -> Nil 
^
    list_head 

И в итоге:

[2] -> [100] -> Nil 
     ^
     list_head 

и аналогично для другого списка. Так что, насколько вы обеспокоены в этот момент, вы просто объединяете два списка размера один, что вы делаете правильно - вот как вы закончили с 37 и 100.

Это должно указывать на правильное направление.