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
{
element_t *sorted = NULL;

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

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

// Update current
current = next;
}

}

/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
{
element_t* current;
/* Special case for the head end */
{
}
else
{
/* Locate the node before the point of insertion */
while (current->next!=NULL &&
current->next->val < new_node->val)
{
current = current->next;
}
new_node->next = current->next;

current->next = new_node;
}
}
• Can you provide a minimum working example, especially with the kind of data you're using as input? Also, it would be nice to know what you mean by "much longer", and "usual". Aug 8 '16 at 8:31

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;

counti++;  // *****

} else {

counti++;  // *****

while (current->next != NULL && current->next->val < new_node->val) {

counti++;  // *****

current = current->next;
}
new_node->next = current->next;
current->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.