# 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, 2016 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.