title: Sorting doubly linked list in c
body: <p>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).</p>
  
  <p>Thanks for your help.</p>
  
  <p>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?</p>
  
  <p>My code (for simplicity, I omitted the prev node in the node struct):</p>
  
  <pre><code>struct node {
      int number;
      struct node *next;
  };
  </code></pre>
  
  <p>Insertion sort :</p>
  
  <pre><code>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-&gt;number = value;
      /* If the first element */
      if (head == NULL) {
          new_node-&gt;next = NULL;
          head = new_node;
      } 
  
      else if (new_node-&gt;number &lt; head-&gt;number) {
          new_node-&gt;next = head;
          head = new_node;    
      } 
  
      else {
          cur_node = head;
          found = 0;
          while (( cur_node != NULL ) &amp;&amp; ( found == 0 )) {
              if( new_node-&gt;number &lt; cur_node-&gt;number )
              {
                  found = 1;
              }
              else
              {
                  last_node = cur_node;
                  cur_node = cur_node-&gt;next;
              }
          }
      /* We got the right place to insert our node */
      if( found == 1 )
      {
          new_node-&gt;next = cur_node; 
      }
      /* Insert at the tail of the list */
      else
      {
          last_node-&gt;next = new_node;
          new_node-&gt;next = NULL;
      }           
  }
  </code></pre>
  
  <p>Merge Sort :</p>
  
  <pre><code>/* 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-&gt;number = number;
          tnode-&gt;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-&gt;next == NULL))
          return head;
  
      head_one = head;
      head_two = head-&gt;next;
      while((head_two != NULL) &amp;&amp; (head_two-&gt;next != NULL)) {
          head = head-&gt;next;
          head_two = head-&gt;next-&gt;next;
      }
      head_two = head-&gt;next;
      head-&gt;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-&gt;number &lt; head_two-&gt;number) {
          head_three = head_one;
          head_three-&gt;next = merge(head_one-&gt;next, head_two);
      } else {
          head_three = head_two;
          head_three-&gt;next = merge(head_one, head_two-&gt;next);
      }
  
      return head_three;
  }
  </code></pre>