then which sort is inefficient?

0 votes

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

0 votes

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)

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)

0 votes

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