CareerCup

The main reason is because for LinkedList, it doesn't need auxiliary space when merging.

Implementation of merge sort is here:
a. Split the linked list into two halves.
b. Call mergesort recursively for both the halves.
c. At last merge the two sorted halves

#include <stdio.h>
#include <stdlib.h>

typedef struct node node_t;

struct node
{
    int data;
    node_t *next;
};
void push(node_t **head_ref,int data)
{
    node_t *n=(node_t *)malloc(sizeof(node_t));
    n->data=data;
    n->next=(*head_ref);
    (*head_ref)=n;
}
void splitLinkedList(node_t *source,node_t **fr,node_t **br)
{
    node_t *fast,*slow;
    if(source==NULL||source->next==NULL)
    {
        *fr=source;
        *br=NULL;
    }
    else
    {
        slow=source;
        fast=source->next;
        while(fast!=NULL)
        {
            fast=fast->next;
            if(fast!=NULL)
            {
                slow=slow->next;
                fast=fast->next;
            }
        }
        *fr=source;
        *br=slow->next;
        slow->next=NULL;
    }
}
node_t *sortedMerge(node_t *a,node_t *b)
{
    node_t *result=NULL;
    if(a==NULL)
        return b;
    else if(b==NULL)
        return a;
    else if(a->data <= b->data)
    {
        result=a;
        result->next=sortedMerge(a->next,b);
    }
    else
    {
        result=b;
        result->next=sortedMerge(a,b->next);
    }
    return result;
}
void mergeSort(node_t **head_ref)
{
    node_t *head=*head_ref;
    node_t *a,*b;
    if(head==NULL||head->next==NULL)
        return;
    splitLinkedList(head,&a,&b);
    mergeSort(&a);
    mergeSort(&b);
    *head_ref=sortedMerge(a,b);
}
void printList(node_t *head)
{
    node_t *temp=head;
    while(temp!=NULL)
    {
        printf(" %d ",temp->data);
        temp=temp->next;
    }
}
int main()
{
    node_t *head=NULL;
    push(&head,1);
    push(&head,5);
    push(&head,3);
    push(&head,6);
    push(&head,4);
    printList(head);
    mergeSort(&head);
    printf("\n");
    printList(head);
}

Isn't an array same as linked list from the usage point of view for a merge sort (traversal and swaps)?

Take a look at the following explanation by Simon Tatham, of Putty fame.

www .chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Take a look at the following explanation by Simon Tatham, of Putty fame.

www .chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

In linked listes no need to do the sorting with the help of another list rather with two lists merging can be done

python code

a=[1,3,5,7,8,12,34,45,67,90]
b=[17,23,34,36,48,79,80,88]
while i<len(a) and j<len(b):
 if a[i]>b[j]:
     a.insert(i,b[j])
      j+=1
      i+=1
 i+=1

print a

In linked listes no need to do the sorting with the help of another list rather with two lists merging can be done

python code

a=[1,3,5,7,8,12,34,45,67,90]
b=[17,23,34,36,48,79,80,88]
while i<len(a) and j<len(b):
 if a[i]>b[j]:
     a.insert(i,b[j])
      j+=1
      i+=1
 i+=1

print a

Quicksort is slightly sensitive to input that happens to be in the right order, in which case it can skip some swaps. Mergesort doesn't have any such optimizations, which also makes Quicksort a bit faster compared to Mergesort.

Below link can be useful to find out the more difference and to know more about quicksort and mergesort

newtechnobuzzz.blogspot.in/2014/07/why-quicksort-is-better-than-mergesort.html

Normally, Quick Sort is considered to better sorting algorithm than Merge sort. But , to explain why Merge sort is good for Linked List,  we have to look into disadvantage of Quick sort when we use it for Linked List. 

Quick sort has locality of reference, where the computer hardware is optimized so that accessing memory locations that are near one another tends to be faster than accessing memory locations scattered throughout memory. The partitioning step in quick sort typically has excellent locality, since it accesses consecutive array elements near the front and the back. 

But when working with linked lists, this advantage necessarily will not apply. Because linked list cells are often scattered throughout memory, there is no locality bonus to accessing adjacent linked list cells. Also, since merge sort's linked list algorithm doesn't need any extra auxiliary storage space and it more evenly splits the lists in half and does less work per iteration to do a merge than to do the partitioning step like quick sort, merge sort is going to be better for linked list.


namespace CommonElementsOfTwoLinkedList
{
class Program
    {
        static void Main(string[] args)
        {
            List l1 = new List();
            l1.Add(1);
            l1.Add(2);
            l1.Add(6);
            l1.Add(12);
            l1.Add(14);
            l1.Add(18);
            l1.Print();
                  

            
            Node result = SortList.MergeSort(l1);
        }
    }
   class SortList
   {

      
       public Node Merge(Node list1, Node list2)
       {
           Node result = null;
           if (list1 == null)
               return list2;
           if (list2 == null)
               return list1;
           if (list1.ID <= list2.ID)
           {
               result = list1;
               result.Front = Merge(list1.Front, list2);
           }
           else
           {
               result = list2;
               result.Front = Merge(list1, list2.Front);
           }
           return result;
       }

       public Node MergeSort(Node list1)
       {
           if (list1 == null || list1.Front == null)
           {
               return list1;
           }
           Node head_one = list1, head_two;
           head_two = list1.Front;
           while (head_two != null && head_two.Front != null)
           {
               list1 = list1.Front;
               head_two = head_two.Front.Front;
           }
           head_two = list1.Front;
           list1.Front = null;
           return Merge(MergeSort(head_one), MergeSort(head_two));
            }
   }
}

Merge Sort requires a lot of rearrangement in a elements which increases unnecessary complexity in case we use Array....
Linked List is always best option where-ever a lot of element re-ordering is required.

for ex:

4 3 2 1
sort 4,3 and 2,1
Reorder: 3,4,1,2 [4 element changed their order]
sort 3,4,1,2
Reorder: 1,2,3,4 [again 4 element changed their order]

In case Array: We requires many swapping and re ordering for n numbers in worst case. O(n)
Linked List: Breaking and re arranging links does need only O(1) element operation

Yes merge sort is better for all the data structures where insertion and deletion is easier.

For a more comprehensive explanation, please check my blog post.

techieme.in/techieme/merge-sort/