Sort a List using Merge Sort

Write Merge sort routine for sorting linked list

/*
 * Merge Sort
 */
void MergeSort(nodeptr* headRef) {
    nodeptr head = *headRef;
    nodeptr a;
    nodeptr b;

    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

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

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

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

/*
 * Takes two lists sorted in increasing order, and splices their 
 * nodes together to make one big sorted list which is returned.
 */
nodeptr SortedMerge(nodeptr a, nodeptr b)
{
    nodeptr result = NULL;
    nodeptr* lastPtrRef = &result;

    while (1) {
        if (a == NULL) {
            *lastPtrRef = b;
            break;
        }
        else if (b == NULL) {
            *lastPtrRef = a;
            break;
        }
        if (a->data <= b->data) {
            MoveNode(lastPtrRef, &a);
        } else {
            MoveNode(lastPtrRef, &b);
        }
        lastPtrRef = &((*lastPtrRef)->next);
    }
   
    return(result);
}

/*
 * 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.
 */
void FrontBackSplit(nodeptr source, nodeptr* frontRef, nodeptr* backRef)
{
    nodeptr singlestep = NULL;
    nodeptr doublestep = NULL;
    if(source == NULL) {
        *frontRef = NULL;
        *backRef = NULL;
    } else {
        *frontRef = source;
        doublestep = source->next;
        singlestep = source;
        while(doublestep != NULL) {
            if(doublestep->next != NULL)
                doublestep = doublestep->next->next;
            else 
                break;
            singlestep = singlestep->next;
        }
        *backRef = singlestep->next;
        singlestep->next = NULL;
    }
}

Merge Sort

The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.
Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.

We use this technique to sort a file in the following way. Divide the file into n subfiles of size 1 and merge adjacent (disjoint) pairs of files. we then have approximately n/2 files of size 2. Repeat this process until there is only one file remaining of size n.

Below is the nonrecursive procedure expaining merge sort.

#define NUMELTS  .... // .... is to be put as the number of elements in array.

void MergeSort(int x[], int n)
{
    int aux[NUMLETS], i, j, k, l1, l2, size, u1, u2;
   
    size = 1; / * Merge files of size 1;
    while(size < n) {
        l1 = 0; /* initialize lower bounds of first file */
        k = 0; /* k is index for auxiliary array */
        while(l1+size < n) { /* Check to see if there are two files to merge */
            /* Compute remaining indices */
            l2 = l1+size;
            u1 = l2-1;
            u2 = (l2+size-1 < n) > l2+size-1 : n-1;
            /* proceed through the two subfiles */
            for(i=l1,j=l2;i<=u1 && j<=u2; k++)
                /* Enter smaller into the aux array */
                if(x[i] <= x[j])
                    aux[k]=x[i++];
                else
                    aux[k] = x[j++];
            /* At this point, one of the subfiles has been exhausted.
             * Insert any remaining portions of the other file
             */
            for(;i<=u1;k++)
                aux[k] = x[i++];
            for(;j<=u2;k++)
                aux[k] = x[j++];
            /* advance l1 to start of the next pair of files. */
            l1 = u2 +1;
        }
        /* Copy any remaining single file */
        for(i=l1;k<n;i++)
            aux[k++]=x[i];
        /* Copy aux into x and adjust size */
        for(i=0;i<n;i++)
            x[i]=aux[i];
        size *= 2;
    }
}

Average case time complexity of merge sort is O(nlogn) but it requires O(n) additional space for the auxiliary array.