我要保持一个链表按照排序顺序插入元素（约20列表中的元素），你可以推荐的算法是什么时候？我用插入排序做了一个简单的实现，但它的性能是非常非常坏的（大量的CPU使用率）。

I want to keep a linked list in sorted order when inserting elements (about 200000 elements in the list), which algorithm can you recommend? I made a simple implementation using insertion sort, but its performance is very very bad (a lot of CPU usage).

感谢您的帮助。

我没有合并排序和插入排序之间的一些比较，但似乎插入排序有更好的表现，我有点被这个结果感到困惑。你能告诉我什么是错的，如果有更好的算法？

I did some comparison between merge sort and insertion sort but it seems that insertion sort has better performance, I am a bit confused by this result. Can you tell me what's wrong and if there is a better algorithm?

我的code（为简单起见，我省略了节点结构中的preV节点）：

My code (for simplicity, I omitted the prev node in the node struct):

struct node {
    int number;
    struct node *next;
};

插入排序：

void insert_node(int value) {
    struct node *new_node = NULL;
    struct node *cur_node = NULL;
    struct node *last_node = NULL;
    int found; /* 1 means found a place to insert the new node in, 0 means not*/


    new_node = (struct node *)malloc(sizeof(struct node *));
    if(new_node == NULL) {
        printf("memory problem\n");
    }
    new_node->number = value;
    /* If the first element */
    if (head == NULL) {
        new_node->next = NULL;
        head = new_node;
    } 

    else if (new_node->number < head->number) {
        new_node->next = head;
        head = new_node;    
    } 

    else {
        cur_node = head;
        found = 0;
        while (( cur_node != NULL ) && ( found == 0 )) {
            if( new_node->number < cur_node->number )
            {
                found = 1;
            }
            else
            {
                last_node = cur_node;
                cur_node = cur_node->next;
            }
        }
    /* We got the right place to insert our node */
    if( found == 1 )
    {
        new_node->next = cur_node; 
    }
    /* Insert at the tail of the list */
    else
    {
        last_node->next = new_node;
        new_node->next = NULL;
    }           
}

归并排序：

/* add a node to the linked list */
struct node *addnode(int number, struct node *next) {
    struct node *tnode;

    tnode = (struct node*)malloc(sizeof(*tnode));

    if(tnode != NULL) {
        tnode->number = number;
        tnode->next = next;
    }

    return tnode;
}

/* perform merge sort on the linked list */
struct node *merge_sort(struct node *head) {
    struct node *head_one;
    struct node *head_two;

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

    head_one = head;
    head_two = head->next;
    while((head_two != NULL) && (head_two->next != NULL)) {
        head = head->next;
        head_two = head->next->next;
    }
    head_two = head->next;
    head->next = NULL;

    return merge(merge_sort(head_one), merge_sort(head_two));
}

/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two) {
    struct node *head_three;

    if(head_one == NULL)
        return head_two;

    if(head_two == NULL)
        return head_one;

    if(head_one->number < head_two->number) {
        head_three = head_one;
        head_three->next = merge(head_one->next, head_two);
    } else {
        head_three = head_two;
        head_three->next = merge(head_one, head_two->next);
    }

    return head_three;
}

推荐答案

正在不正确地实现合并排序是基于递归分割列表分成两部分，它们排序和合并的结果。但是，在你的code，你真的不将列表分为两部分。

You are not correctly implementing the merge sort which is based on recursively dividing the list into two parts, sorting them and merging the result. But in your code, you don't really divide the list into two halves.

注意，在这个行：

while((head_two != NULL) && (head_two->next != NULL)) {
    head = head->next;
    head_two = head->next->next;
}
head_two = head->next;
head->next = NULL;

您退出while循环时head_two到达列表的末尾：例如，如果你达到 head_two-＆gt;接下来== NULL 在循环，那么你就退出它与流浆＆GT;下一步 - ＆gt;接下来== NULL 。当你运行 head_two =流浆＆gt;接下来，，你会得到一个 head_two ，使得 head_two-＆gt;接下来== NULL 这是列表中的最后一项

you exit the while loop when head_two reaches the end of the list: If for example you reach head_two->next == NULL at the loop, then you exit it with head->next->next == NULL. And when you run head_two = head->next;, you get a head_two such that head_two->next == NULL which is the last item in the list.

这意味着你基本上是做一个插入排序，而不是合并排序。

That means that you are basically doing an insertion sort and not a merge sort.

因此​​，尝试，通过添加参数长度的功能来跟踪列表的长度 merge_sort 要能够将其拆分成2。这里是算法在维基百科

So try to keep track of the length of the list, by adding a parameter length to the function merge_sort to be able to split it into 2. Here is a good explanation of the algorithm in wikipedia.