mergesort.h

对链表进行排序 应用了多种排序方法 对其进行比较 有自己的详细的时间函数

Node* merge(Node*first,Node*second) 
{ 
   Node* head   =   new Node; 
   Node*current; 
   current=head; 
   while(first   !=   NULL   &&   second   !=NULL) 
  { 
     if(first->data   <   second-> data) 
     { 
        current-> next   =   first; 
        first   =   first-> next; 
        current   =   current-> next; 
     } 
     else
     { 
      current-> next   =   second; 
      second   =   second-> next; 
      current   =   current-> next; 
     } 
  } 

     while(first   !=   NULL) 
     { 
        current-> next   =   first; 
        first   =   first-> next; 
        current   =   current-> next; 
     } 
     while(second   !=   NULL) 
    { 
      current-> next   =   second; 
      second   =   second-> next; 
      current   =   current-> next; 
    } 

     return   head-> next; 
} 


Node*  MergeSort(Node*toSortList) 
{ 
    Node* first;
    Node* second;
    first  = toSortList; 
    second = toSortList->next; 

    if(first == NULL || second == NULL) return toSortList; 

    while(second != NULL && second->next != NULL) 
    { 
        toSortList = toSortList-> next; 
        second =  second->next->next;  //填空
    } 

    second = toSortList->next;  //填空
    toSortList->next = NULL;    //填空

    return   merge(MergeSort(first), MergeSort(second)); 
}