Insertion sort of a linked list

Question

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->next;
 // insert current in sorted linked list
 sortedInsert(&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)->val >= new_node->val)
 {
 new_node->next = *head_ref;
 *head_ref = new_node;
 }
 else
 {
 /* Locate the node before the point of insertion */
 current = *head_ref;
 while (current->next!=NULL &&
 current->next->val < new_node->val)
 {
 current = current->next;
 }
 new_node->next = current->next;
current->next = new_node;
 }
}

• ChatterOne: 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".

Answer 1

Code performs as expected.

Insertion sort has an expected O(n²) performance and OP's code has about 0.25*n² 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)->val >= new_node->val) {
 counti++; // *****
 new_node->next = *head_ref;
 *head_ref = new_node;
 } else {
 current = *head_ref;
 counti++; // *****
 while (current->next != NULL && current->next->val < new_node->val) {
 counti++; // *****
 current = current->next;
 }
 new_node->next = current->next;
 current->next = new_node;
 }
}

Compare Count vs. List Length

No functional implementation problem found.

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