search
Log In
0 votes
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 166 views

2 Answers

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)
0
then which sort is inefficient?
0
Mergesort will also 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

Related questions

0 votes
1 answer
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
asked Jun 28, 2017 in DS Arnab Bhadra 344 views
0 votes
2 answers
2
503 views
Which of the following operations is performed more efficiently by doubly linked list than by singly linked list? (a) Deleting a node whose location in given (b) Searching of an unsorted list for a given item (c) Inverting a node after the node with given location (d) Traversing a list to ... list :- q->next = q->next->next; free(q->next); it is easy to delete in singly than in doubly. crct me?
asked Jun 6, 2017 in Algorithms Shubhanshu 503 views
0 votes
1 answer
3
185 views
What does the following program do on two linked lists? Struct node *myFun (struct node * a, struct node * b) { Struct node *new = NULL ; If (a = = NULL) return (b) ; if (b = = NULL) return (a) ; If (a → data <= b → ... merges two linked lists by selecting the alternate nodes merges two sorted linked lists into final sorted linked list merges two linked lists by selecting the nodes in reverse.
asked Dec 27, 2018 in DS sharadsingh 185 views
0 votes
0 answers
4
242 views
int find (struct node * first, int n) { while (first data ! = n) first = first — next; if (first data = = n) return(1); else return (-1); in the above code segment if the value of 'n' is 5, then the function return 1, but if the value of 'n' is 9, then what does it do ?
asked Dec 5, 2018 in DS Mk Utkarsh 242 views
...