Self Doubt on Linked List

Question

Can somebody write the code or algorithm, how merge sort works efficiently in linked list? Is Heap sort most inefficient in Linked List Sorting? Elaborate plz

Answer 1

struct node* MS(struct node* s, struct node*s1, struct node*s2){

if(s == NULL) return(NULL);

else if(s->next == NULL) return(s);

else{

b = middle(s);

q = b->next;

b->next = NULL;

s1 = MS(s);

s2 = MS(q);

s = merge(s1,s2);

return (s);

}}


No heapsort is not the most inefficient in linked list sorting because it will take O(nlogn)

Comments

then which sort is inefficient?

---

Mergesort will also take o ( nlogn)

Answer 2

MergeSort(headRef)
1) If the head is NULL or there is only one element in the Linked List 
    then return.
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.
      MergeSort(a);
      MergeSort(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.

Ref: https://gateoverflow.in/196252/linked-list

https://stackoverflow.com/questions/10885449/heap-sort-using-linked-lists