연결리스트를 이용한 병합정렬(천만개의 정수자료 정렬)

http://www.geeksforgeeks.org/merge-sort-for-linked-list/

위의 출처에서 가져온 코드를 수정한 것입니다.

#include<stdio.h>

#include<stdlib.h>

#include<time.h>  

// Link list node 

typedef struct _node *pnode;

typedef struct _node {

    int data;

    pnode next;

} node;

 

// function prototypes 

pnode SortedMerge(pnode a, pnode b);

void FrontBackSplit(pnode source, pnode *frontRef, pnode *backRef);

 

// sorts the linked list by changing next pointers (not data) 

void MergeSort(pnode *headRef) {

    pnode head = *headRef;

    pnode a;

    pnode 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 

pnode SortedMerge(pnode  a, pnode b) {

    pnode result = NULL;

    pnode p;

 

    // Base cases 

    if (a == NULL) {

        return(b);

    } else if (b==NULL) {

        return(a);

    }

     

    if(a->data <= b->data) {

        result=a;

        a=a->next;

    } else {

        result=b;

        b=b->next;

    }

    p=result;

    while(a!=NULL && b!=NULL) {

    // Pick either a or b, 

        if (a->data <= b->data) {

            p->next = a;

            a=a->next;

            p=p->next;

        } else {

            p->next = b;

            b=b->next;

            p=p->next;

        }

    }

    if(a==NULL) {

        p->next=b;

    } else {

        p->next=a;

    }

   

    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(pnode source,

          pnode *frontRef, pnode *backRef) {

    pnode fast;

    pnode slow;

    if (source==NULL || source->next==NULL) {

        // length < 2 cases 

        *frontRef = source;

        *backRef = NULL;

    } else {

        slow = source;

        fast = source->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(pnode node) {

    int i=0;

    while(node!=NULL) {

        if(i<1000 || i%10000==0)

            printf("%d ", node->data);

        i+=1;

        node = node->next;

    }

}

 

// Function to insert a node at the beginging of the linked list 

void push(pnode *head_ref, int new_data) {

    // allocate node 

    pnode new_node = (pnode) malloc(sizeof(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;

} 

  

// Driver program to test above functions

int main() {

    // Start with the empty list 

    pnode res = NULL;

    pnode a = NULL;

    int i, n=10000000, x, y, z;

  

    // Let us create a unsorted linked lists to test the functions

    // Created lists shall be a: 2->3->20->5->10->15 

    srand(time(NULL));

    for(i=0;i<n;i+=1) {

        x=rand(); y=rand(); z=(x<<15)|y;

        push(&a, z);

    }

    printList(a);

    // Sort the above created Linked List 

    MergeSort(&a);

  

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

    printList(a);           

  

    printf("\nFinished\n");

  

    return 0;

}