0
\$\begingroup\$

(See the next iteration.)

I have this C implementation of the merge sort for sorting singly-linked lists:

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

typedef struct linked_list_node {
    int value;
    struct linked_list_node* next;
} linked_list_node;

/*******************************************************************************
* This fuction converts the command line arguments to a linked list.           *
*******************************************************************************/
static linked_list_node* build_linked_list_from_args(int argc, const char* argv[])
{
    if (argc <= 1)
    {
        return NULL;
    }

    linked_list_node* head = malloc(sizeof(*head));
    linked_list_node* tail = head;

    head->value = atoi(argv[1]);

    for (size_t arg_index = 2; arg_index < argc; ++arg_index)
    {
        linked_list_node* new_node = malloc(sizeof(*new_node));
        new_node->value = atoi(argv[arg_index]);
        tail->next = new_node;
        tail = new_node;
    }

    tail->next = NULL;
    return head;
}

/*******************************************************************************
* This function prints the entire linked list to stdout.                       *
*******************************************************************************/
static void print(linked_list_node* head)
{
    printf("[");
    linked_list_node* current_node = head;

    if (current_node)
    {
        printf("%d", current_node->value);
        current_node = current_node->next;
    }

    while (current_node)
    {
        printf(" %d", current_node->value);
        current_node = current_node->next;
    }

    printf("]");
}

static linked_list_node* merge(linked_list_node* left_head,
                               linked_list_node* right_head)
{
    linked_list_node* merged_list_head;
    linked_list_node* merged_list_tail;

    if (right_head->value < left_head->value)
    {
        merged_list_head = right_head;
        merged_list_tail = right_head;
        right_head = right_head->next;
    }
    else
    {
        merged_list_head = left_head;
        merged_list_tail = left_head;
        left_head = left_head->next;
    }

    while (left_head && right_head)
    {
        if (right_head->value < left_head->value)
        {
            merged_list_tail->next = right_head;
            merged_list_tail = right_head;
            right_head = right_head->next;
        }
        else
        {
            merged_list_tail->next = left_head;
            merged_list_tail = left_head;
            left_head = left_head->next;
        }
    }

    merged_list_tail->next = left_head ? left_head : right_head;
    return merged_list_head;
}

/*******************************************************************************
* This function implements the actual sorting routine.                         *
*******************************************************************************/
static linked_list_node* sort_impl(linked_list_node* head)
{
    if (!head->next)
    {
        return head;
    }

    linked_list_node* left_sublist_head  = head;
    linked_list_node* right_sublist_head = head->next;

    linked_list_node* left_sublist_tail  = left_sublist_head;
    linked_list_node* right_sublist_tail = right_sublist_head;

    linked_list_node* current_node = right_sublist_tail->next;

    bool left = true;

    // Split the input linked list into two sublist of almost the same length:
    while (current_node)
    {
        if (left)
        {
            left_sublist_tail->next = current_node;
            left_sublist_tail = current_node;
            left = false;
        }
        else
        {
            right_sublist_tail->next = current_node;
            right_sublist_tail = current_node;
            left = true;
        }

        current_node = current_node->next;
    }

    left_sublist_tail ->next = NULL;
    right_sublist_tail->next = NULL;

    return merge(sort_impl(left_sublist_head),
                 sort_impl(right_sublist_head));
}

/*******************************************************************************
* This function sorts the input linked list whose the first node is 'head'.    *
*******************************************************************************/
linked_list_node* sort(linked_list_node* head)
{
    if (!head || !head->next)
    {
        return head;
    }

    return sort_impl(head);
}

int main(int argc, const char * argv[]) {
    linked_list_node* head = build_linked_list_from_args(argc, argv);
    print(head);
    puts("");
    head = sort(head);
    print(head);
    puts("");
    return 0;
}

So, how am I doing here? Is there anything I could improve?

\$\endgroup\$
2
\$\begingroup\$

Splitting the list the way you do destabilizes sorting. Consider a list x->y->z->... where y and z compare equal. After splitting, y lands into the right sublist, and z into the left. Since left sublist has a priority when merging equal elements, z is merged first.

To maintain stability, the list shall be split in the middle. I also recommend to factor the splittion out into a function, along the lines of

linked_list_node * split(linked_list_node * head)
{
    linked_list_node * slow = head;
    linked_list_node * fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    linked_list_node * right_sublist_head = slow->next;
    slow->next = NULL;
    return right_sublist_head;
}

Building a list can also be streamlined. Since you know the list size in advance, you can get away with a single allocation call:

    linked_list_node * head = calloc(sizeof(*head), argc - 1);
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Note that it makes difference in practice, but calloc expects the number of elements as the first argument, and the size of each element as the second: cplusplus.com/reference/cstdlib/calloc \$\endgroup\$ – coderodde Aug 11 '16 at 15:58
  • \$\begingroup\$ Also, you made a nice point about stability and how to retain it. However, you particular implementation is not flawless as it gave me segmentation fault on small 2-element input lists. \$\endgroup\$ – coderodde Aug 11 '16 at 16:35
0
\$\begingroup\$

I would consider the following:

linked_list_node * make_node(int val, linked_list_node * next){
    linked_list_node * return_node = (linked_list_node *) malloc(sizeof(linked_list_node));
    return_node->value = val;
    return_node->next = next;
    return return_node;
}

Now, adding nodes is trivial, at least for making the linked list from argv. That could become:

linked_list_node * head = NULL, * tail = NULL;
for(int i = 1; i < argc; i++){
    if(tail == NULL){
        head = make_node(atoi(argv[i]), NULL);
        tail = head;
    }else{
        tail->next = make_node(atoi(argv[i]), NULL);
        tail = tail->next;
    }
}

return head;

Printing nodes can also be better written:

printf("[");
for(linked_list_node * temp = head; temp != NULL; temp = temp->next)
    printf("%d%c ", temp->value, (temp->next == NULL)?']':',');

This works in the same way as yours, but the cases are all handled in one place. (In fact, given your while loop header, you don't need the if statement before it.)

The sort itself (other than the aforementioned instability) seems fine.

| improve this answer | |
\$\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.