Article 102 - Mergesort Implementation

This article describes an implementation of the Mergesort Algorithm.

For information about the Mergesort Algorithm, see Article 35 - Programming Sorting Algorithms.

Implementation

In this implementation, we use the Node structure from the Link List Article, see Article 83 - Data Structure - How to Implement Linked List in C.

To make the implementation challenging, we will swap nodes instead of swapping content.

Mergesort implementation.

int mergesort( Node ** list ){
    int listSize = 0;
    int i;
    Node * listPointer;
    Node * list1Pointer;
    Node * list2Pointer;    
    
    if( !list ){
        return -1;
    }

    if( !*list ){
        return 0;
    }

    //divide list into two after counting size of original list
    for( listPointer = *list; listPointer; 
        listPointer = listPointer->next ){
        listSize++;
    }    

    i = listSize / 2;

    for( listPointer = *list; i > 0; i-- ){
        listPointer = listPointer->next;
    } 

    list2Pointer = listPointer->next;
    listPointer->next = 0;

    list1Pointer = *list;

    //recursively mergesort both lists
    if( mergesort( &list1Pointer ) ){
        return -3;
    }

    if( mergesort( &list2Pointer ) ){
        return -3;
    }

    //need first node, take smaller of two
    if( list2Pointer ){
        if( list1Pointer->content < list2Pointer->content ){
            listPointer = list1Pointer;
            list1Pointer = list1Pointer->next;
        }
        else{
            listPointer = list2Pointer;
            list2Pointer = list2Pointer->next;
        }

        *list = listPointer;

        //iterate through both lists and pick the next smallest
        for( ; list1Pointer || list2Pointer; ){
            if( list1Pointer && list2Pointer ){
                if( list1Pointer->content < list2Pointer->content ){
                    listPointer->next = list1Pointer;
                    list1Pointer = list1Pointer->next;
                }
                else{
                    listPointer->next = list2Pointer;
                    list2Pointer = list2Pointer->next;
                }
            }
            else if( list1Pointer ){
                listPointer->next = list1Pointer;
                break;
            }
            else{
                listPointer->next = list2Pointer;
                break;
            }

            listPointer = listPointer->next;
        }
    }
    else{
        *list = list1Pointer;
    }

    return 0;
}

Comments (1)

Posted by anonymous - NV at Tuesday, April 2, 2013 1:56 PM

Works great!

How to do this in place?

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2023. Vantasy World is a project developed by Vantasy Online. Privacy Policy.