Perhaps you've overcomplicated it. You could ignore the case where an item is greater than all items inserted thus far:
Code:
template <class TItem>
void InsertionSort(TItem *&head) {
TItem *newList = NULL, *oldList = head;
while (oldList != NULL) {
//take an item off the old list
TItem *temp = oldList;
oldList = oldList->next;
TItem *curr = newList, *prev = NULL;
//find the place in the new list for this item
while (curr != NULL) {
if (*temp < *curr)
break;
prev = curr;
curr = curr->next;
}
//put the item in the new list
if (prev == NULL)
newList = temp;
else
prev->next = temp;
temp->next = curr;
}
head = newList;
}
Sure that's slower for an already sorted list, but we're not using InsertionSort for sorting long lists anyway, if we know what's good for us.