Answer is Heap sort as it most dependent on random access which is costly in case on Linked List.
Merge Sort for Linked Lists:
Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
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);
Time Complexity: O(n Log n)
Quick Sort on Linked List:
1. Take rightmost element as the pivot
Traverse through the list
a. If the node has value greater than pivot, we will move it after tail
b. else, keep it in same position
1. Call Partition(), which places pivot at right position and returns the pivot
2. Find the tail node of the left sublist ie, left side of the pivot and recur for left list
3. Now, recur for right list
Below is simple insertion sort algorithm for linked list.
1) Create an empty sorted (or result) list
2) Traverse the given list, do following for every node.
......a) Insert current node in sorted way in sorted or result list.
3) Change head of given linked list to head of sorted (or result) list
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.