鏈表歸併排序Exaplanation

Question

有人可以解釋給我聽聽，多麼此代碼的工作：

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c

我不明白，在這個帖子中使用的算法。謝謝

Answer 1

嘗試將在數組上正常合併排序中執行的所有合併成像：首先，將元素配對併合併爲長度爲2的有序子數組，然後將這些長度爲2的子數組配對併合併爲排序長度爲四的子陣列等等。請注意子數組的長度：1,2,4等等，我們稱之爲instep，這在每次迭代中都會加倍。

在任何時候，p點長度instep，q點長度instep或更小的列表的列表（我們可能會碰到列表的末尾），和q緊跟p。如上所述，它們形成一對子陣列。我們在p和q上進行合併以獲得從p開始的長度爲psize + qsize的排序列表。我們將p和q移至下一對，依此類推。一旦我們完成了整個列表，我們加倍instep並開始合併更長的排序列表。

Answer 2

合併排序通常是排序鏈接列表的首選。鏈表的慢速隨機訪問性能使其他一些算法（如quicksort）表現不佳，而其他算法（如堆排序）則完全不可能。

讓head是要排序的鏈表的第一個節點，headRef是指向head的指針。請注意，我們需要對MergeSort（）中的頭進行引用，因爲下面的實現會更改下一個鏈接來對鏈接列表進行排序（不是節點上的數據），所以如果原始頭部的數據不是最小值，則必須更改頭節點在鏈表中。

歸併（headRef）

1）如果頭是NULL或僅存在一個鏈表 元件然後返回。

2）否則將鏈表分成兩半。 FrontBackSplit（head，&a，&b）;/* a和b是兩半*/

3）對兩半a和b進行排序。 MergeSort（a）; MergeSort（b）;

4）合併排序後的a和b（使用此處討論的SortedMerge（）） 並使用headRef更新頭指針。 * headRef = SortedMerge（a，b）;

 




    /* Link list node */ 
    struct node 
    { 
     int data; 
     struct node* next; 
    }; 

    /* function prototypes */ 
    struct node* SortedMerge(struct node* a, struct node* b); 
    void FrontBackSplit(struct node* source, 
       struct node** frontRef, struct node** backRef); 

    /* sorts the linked list by changing next pointers (not data) */ 
    void MergeSort(struct node** headRef) 
    { 
     struct node* head = *headRef; 
     struct node* a; 
     struct node* b; 

     /* Base case -- length 0 or 1 */ 
     if ((head == NULL) || (head->next == NULL)) 
     { 
     return; 
     } 

     /* Split head into 'a' and 'b' sublists */ 
     FrontBackSplit(head, &a, &b); 

     /* Recursively sort the sublists */ 
     MergeSort(&a); 
     MergeSort(&b); 

     /* answer = merge the two sorted lists together */ 
     *headRef = SortedMerge(a, b); 
    } 

    /* See http://geeksforgeeks.org/?p=3622 for details of this 
     function */ 
    struct node* SortedMerge(struct node* a, struct node* b) 
    { 
     struct node* result = NULL; 

     /* Base cases */ 
     if (a == NULL) 
     return(b); 
     else if (b==NULL) 
     return(a); 

     /* Pick either a or b, and recur */ 
     if (a->data data) 
     { 
     result = a; 
     result->next = SortedMerge(a->next, b); 
     } 
     else 
     { 
     result = b; 
     result->next = SortedMerge(a, b->next); 
     } 
     return(result); 
    } 

    /* UTILITY FUNCTIONS */ 
    /* Split the nodes of the given list into front and back halves, 
     and return the two lists using the reference parameters. 
     If the length is odd, the extra node should go in the front list. 
     Uses the fast/slow pointer strategy. */ 
    void FrontBackSplit(struct node* source, 
       struct node** frontRef, struct node** backRef) 
    { 
     struct node* fast; 
     struct node* slow; 
     if (source==NULL || source->next==NULL) 
     { 
     /* length next; 

     /* Advance 'fast' two nodes, and advance 'slow' one node */ 
     while (fast != NULL) 
     { 
      fast = fast->next; 
      if (fast != NULL) 
      { 
      slow = slow->next; 
      fast = fast->next; 
      } 
     } 

     /* 'slow' is before the midpoint in the list, so split it in two 
      at that point. */ 
     *frontRef = source; 
     *backRef = slow->next; 
     slow->next = NULL; 
     } 
    } 

    /* Function to print nodes in a given linked list */ 
    void printList(struct node *node) 
    { 
     while(node!=NULL) 
     { 
     printf("%d ", node->data); 
     node = node->next; 
     } 
    } 

    /* Function to insert a node at the beginging of the linked list */ 
    void push(struct node** head_ref, int new_data) 
    { 
     /* allocate node */ 
     struct node* new_node = 
       (struct node*) malloc(sizeof(struct node)); 

     /* put in the data */ 
     new_node->data = new_data; 

     /* link the old list off the new node */ 
     new_node->next = (*head_ref);  

     /* move the head to point to the new node */ 
     (*head_ref) = new_node; 
    } 

    /* Drier program to test above functions*/ 
    int main() 
    { 
     /* Start with the empty list */ 
     struct node* res = NULL; 
     struct node* a = NULL; 
     struct node* b = NULL; 

     /* Let us create a unsorted linked lists to test the functions 
     Created lists shall be a: 2->3->20->5->10->15 */ 
     push(&a, 15); 
     push(&a, 10); 
     push(&a, 5); 
     push(&a, 20); 
     push(&a, 3); 
     push(&a, 2); 

     /* Remove duplicates from linked list */ 
     MergeSort(&a); 

     printf("\n Sorted Linked List is: \n"); 
     printList(a);   

     getchar(); 
     return 0; 
    }