3
\$\begingroup\$

This is my version of a linked list in C. The function mergeSort requires a reference to the first and to the last nodes, as well as the indices of the first and the last node and a comparator.

You need to compile this source code using C99 standard in order to get it working.

#include <stdio.h>
#include <stdlib.h>

typedef struct List {
    int val;
    struct List *next;
} List; 

List *new(int value)
{
    List *list = malloc(sizeof(List));
    list->next = NULL;
    list->val = value;

    return list;
}

void freeList(List *list)
{
    List *node = list;
    while(node != NULL) {
        List *n = node->next;
        free(node);
        node = n;
    } 
}

void print(List *list)
{
    for(List *node = list; node != NULL; node = node->next) {
        printf("%d ", node->val);        
    }
    printf("\n");
}

List *merge(List *part1, List *part2, int (*cmp)(const void *, const void *))
{
    List *temp;

    if(cmp(&part1->val, &part2->val) < 0) {
        temp = part1;
        part1 = part1->next;    
    }   
    else {
        temp = part2;
        part2 = part2->next;
    }

    List *current = temp;

    while(part1 != NULL && part2 != NULL) {
        if(cmp(&part1->val, &part2->val) < 0) {
            current->next = part1;
            part1 = part1->next;
        }
        else {
            current->next = part2;
            part2 = part2->next;
        }
        current = current->next;
    }

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

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

    return temp;
}

List *mergeSort(List *start,
                List *stop,
                int startIndex,
                int stopIndex,
                int (*cmp)(const void *, const void *))
{
    if(start != stop) {
        int mid = (startIndex + stopIndex) / 2;
        int i = startIndex;

        List *midNode = NULL;
        for(List *node = start; node != stop; node = node->next) {
            if(i == mid) {
                midNode = node;
            } 
            i++;
        }
        List *midNodeNext = midNode->next;

        List *part1 = mergeSort(start, midNode, startIndex, mid, cmp);
        List *part2 = mergeSort(midNodeNext, stop, mid + 1, stopIndex, cmp);

        return merge(part1, part2, cmp);
    }

    start->next = NULL;
    return start;
}

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

List *push(List *list, List *node) 
{
    List *last;
    for(List *node = list; node != NULL; node = node->next) {
        if(node->next == NULL) {
            last = node;
        }
    }
    last->next = node;

    return node;
}

int main()
{
    List *list = new(9);

    push(list, new(4));
    push(list, new(3));
    push(list, new(2));
    push(list, new(1));
    List *stop = push(list, new(8));

    list = mergeSort(list, stop, 0, 5, cmp);

    print(list);

    freeList(list);

    return 0;

}
\$\endgroup\$
  • \$\begingroup\$ new() is not a great name for a function. Maybe newNode() \$\endgroup\$ – Martin York Mar 27 '15 at 20:22
2
\$\begingroup\$
  • Merging tails effectively wastes cycles. The nodes are already linked correctly.

        if (part1 != NULL) {
            current->next = part1;
        }
    
        if (part2 != NULL) {
            current->next = part2;
        }
    

    is enough.

  • A single most important feature of merge sort is stability: elements compared equal remain in the original order. A comparison

        if(cmp(&part1->val, &part2->val) < 0)
    

    makes your sort unstable. A correct comparison is either one of

        if(cmp(&part2->val, &part1->val) > 0)
        if(cmp(&part1->val, &part2->val) <= 0)
    
  • Less indentation is easier to follow. I recommend to invert a recursion termination condition:

        if (start == stop) {
            start->next = NULL;
            return start;
        }
        ...
    
  • Avoid naked loops. The

        for(List *node = start; node != stop; node = node->next) {
            if(i == mid) {
                midNode = node;
            }
            i++;
        }
    

    should be factored out into a function

        List * advance(List * start, int steps);
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.