Insertion sort of a linked list This is supposed to be efficient code, but it's taking much longer than what a normal insertion sort would take. I can't identify what's the problem with this insertion sort. Is there an implementation problem?

// function to sort a singly linked list using insertion sort
    void insertionSort(element_t **head_ref)
{
    // Initialize sorted linked list
    element_t *sorted = NULL;

    // Traverse the given linked list and insert every
    // node to sorted
    element_t *current = *head_ref;
    while (current != NULL)
    {
        // Store next for next iteration
        element_t *next = current-&gt;next;

        // insert current in sorted linked list
        sortedInsert(&amp;sorted, current);

        // Update current
        current = next;
    }

    // Update head_ref to point to sorted linked list
    *head_ref = sorted;
}


/* function to insert a new_node in a list. Note that this
  function expects a pointer to head_ref as this can modify the
  head of the input linked list (similar to push())*/
void sortedInsert(element_t** head_ref, element_t* new_node)
{
    element_t* current;
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)-&gt;val &gt;= new_node-&gt;val)
    {
        new_node-&gt;next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        /* Locate the node before the point of insertion */
        current = *head_ref;
        while (current-&gt;next!=NULL &amp;&amp;
               current-&gt;next-&gt;val &lt; new_node-&gt;val)
        {
            current = current-&gt;next;
        }
        new_node-&gt;next = current-&gt;next;




current-&gt;next = new_node;
    }
}
Code performs as expected.

Insertion sort has an expected O(n2) performance and OP's code has about 0.25*n2 compares per length n of a linked list.

By adding a counti to sortedInsert() and providing various length lists with random data to insertionSort(), the below graph was determined.

void sortedInsert(element_t** head_ref, element_t* new_node) {
  element_t* current;
  if (*head_ref == NULL || (*head_ref)-&gt;val &gt;= new_node-&gt;val) {

    counti++;  // *****

    new_node-&gt;next = *head_ref;
    *head_ref = new_node;
  } else {
    current = *head_ref;

    counti++;  // *****

    while (current-&gt;next != NULL &amp;&amp; current-&gt;next-&gt;val &lt; new_node-&gt;val) {

      counti++;  // *****

      current = current-&gt;next;
    }
    new_node-&gt;next = current-&gt;next;
    current-&gt;next = new_node;
  }
}




No functional implementation problem found.

Lots of review-able issues (format, lack of supporting code, etc.), but OP did not ask for that.