166 views
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
in DS

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)
0
then which sort is inefficient?
0
Mergesort will also take o ( nlogn)
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)
*headRef = SortedMerge(a, b);

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.

Related questions

1
344 views
Insertion of a node into a doubly linked list requires how many changes to various Next and Previous Pointer? A. No Change B. 1 Next , 1 Previous C. 2 Next , 2 Previous D. 3 Next , 3 Previous