1) If the head is NULL or there is only one element in the Linked List
2) Else divide the linked list into two halves.
FrontBackSplit(head, &a, &b); /* a and b are two halves */
3) Sort the two halves a and b.
4) Merge the sorted a and b (using SortedMerge() discussed here)
and update the head pointer using headRef.
*headRef = SortedMerge(a, b);
Heap Sort on Linked List
Heapsort is a good sorting algorithm because it's O(n log n) and it's in-place. However, when you have a linked list heapsort is no longer O(n log n) because it relies on random access to the array, which you do not have in a linked list. So you either lose your in-place attribute (by needing to define a tree-like structure is O(n) space). Or you will need to do without them, but remember that a linked list is O(n) for member lookup. Which brings the runtime complexity to something like O(n^2 log n) which is worse than bubblesort.
O(n log n)
O(n^2 log n)