title: Sorting a linked list in ascending order in C
body: <p>I am working on a program for my C programming course that is supposed to give us experience using linked lists. One of the last parts of the assignment asks for us to take a linked list and sort it in ascending order using prepend or append functions that we wrote earlier in our program. </p>
  
  <pre><code>struct lnode
  {
    int datum;
    struct lnode *next;
  };
  
  
  struct lnode*
  prepend(struct lnode *list, int x)
  {
    struct lnode *node = (struct lnode *)malloc(sizeof(struct lnode));
    node -&gt; datum = x;
    node -&gt; next = list;
    list = node;
    return list;
  }
  
  struct lnode*
  append(struct lnode *list, int x)
  {
    if(list==NULL){
      list = (struct lnode *)malloc(sizeof(struct lnode));
      list -&gt; datum = x;
      list -&gt; next = NULL;
    }else{
      list -&gt; next = append(list-&gt;next,x);li
    }
    return list;
  }
  </code></pre>
  
  <p>Above are both the append and prepend functions which we designed in our class.</p>
  
  <p>Below is the delete fuction, something we also made in class:</p>
  
  <pre><code>struct lnode*
  delete(struct lnode *list, int x)
  {
    struct lnode* tmp;
    if(list == NULL){
      return list;
    }else if(list-&gt; datum == x){
      tmp = list -&gt; next;
      list -&gt; next = NULL;
      free(list);
      list = tmp;
      return list;
    }else{
      list-&gt;next = delete(list-&gt;next,x);
      return list;
    }
  }
  
  int
  find_smallest(struct lnode*list)
  {
    int smallest;
    smallest = list-&gt;datum;
    while(list!=NULL){
      if(list-&gt;datum &lt; smallest){
        smallest = list-&gt;datum;
      }
      list = list-&gt;next;
    }
    return smallest;
  }
  </code></pre>
  
  <p>The function find_smallest takes a linked list as its input and should return the smallest integer value in the linked lists. I've tested this function multiple times and it seems to be working perfectly.</p>
  
  <p>Finally, sort, which is below, should create a new linked list new_list and should append the value of the smallest integer in list and then delete that value from list until list no longer has any values.</p>
  
  <pre><code>struct lnode*
  sort(struct lnode *list)
  {
    struct lnode *new_list;
    while(list != NULL &amp;&amp; list-&gt;next != NULL){
      new_list = append(new_list, find_smallest(list));
      list = delete(list, find_smallest(list));
    }
    return new_list;
  }
  </code></pre>
  
  <p>The issue that I'm having is that it appears I am getting an infinite loop. 
  I ran a test case where I printed the elements of list after each running of the loop where list was originally 5 4 1 2 3 and what printed out was 5 4 2 3 over and over again until I forced the program to stop. So I believe it's only running correctly once?</p>