Using C The implementation for Mergesort given in Section 74

Using C++

The implementation for Mergesort given in Section 7.4 takes an array as input and soils that array. At the beginning of Section 7.4 there is a simple pseudocode implementation for sorting a linked list using Mergesort. Implement both a linked list-based version of Mergesort and the array-based version of Mergesort. and compare and analyze their running times.

Solution

======== Merge Sort for Linked List ==========

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

struct ndod
{
   int data;
   struct ndod* next;
};

struct ndod* srtdMrge(struct ndod* asdc, struct ndod* bsdg);
void FrntBckSplt(struct ndod* source,
       struct ndod** frontRef, struct ndod** backRef);

void MrgSrt(struct ndod** headRef)
{
struct ndod* hd = *headRef;
struct ndod* asdc;
struct ndod* bsdg;

if ((hd == NULL) || (hd->next == NULL))
{
   return;
}

FrntBckSplt(hd, &asdc, &bsdg);

MrgSrt(&asdc);
MrgSrt(&bsdg);

*headRef = srtdMrge(asdc, bsdg);
}

struct ndod* srtdMrge(struct ndod* asdc, struct ndod* bsdg)
{
struct ndod* result = NULL;

if (asdc == NULL)
   return(bsdg);
else if (bsdg==NULL)
   return(asdc);

if (asdc->data <= bsdg->data)
{
   result = asdc;
   result->next = srtdMrge(asdc->next, bsdg);
}
else
{
   result = bsdg;
   result->next = srtdMrge(asdc, bsdg->next);
}
return(result);
}

  
void FrntBckSplt(struct ndod* source,
       struct ndod** frontRef, struct ndod** backRef)
{
struct ndod* fast;
struct ndod* slow;
if (source==NULL || source->next==NULL)
{
  
   *frontRef = source;
   *backRef = NULL;
}
else
{
   slow = source;
   fast = source->next;

  
   while (fast != NULL)
   {
   fast = fast->next;
   if (fast != NULL)
   {
       slow = slow->next;
       fast = fast->next;
   }
   }

  
   *frontRef = source;
   *backRef = slow->next;
   slow->next = NULL;
}
}

void printList(struct ndod *ndod)
{
while(ndod!=NULL)
{
printf(\"%d \", ndod->data);
ndod = ndod->next;
}
}

void push(struct ndod** head_ref, int new_data)
{

struct ndod* new_node =
           (struct ndod*) malloc(sizeof(struct ndod));

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;
}

int main()
{

struct ndod* res = NULL;
struct ndod* asdc = NULL;

push(&asdc, 15);
push(&asdc, 10);
push(&asdc, 5);
push(&asdc, 20);
push(&asdc, 3);
push(&asdc, 2);

MrgSrt(&asdc);

printf(\"\ Sorted Linked List is: \ \");
printList(asdc);         

getchar();
return 0;
}

Time Complexity: O(nLogn)

=========== Merge Sort for Array===============

#include <iostream>
#include<cstdlib>
using namespace std;

void mrgArray(int *jkj, int lo, int min, int hi)
{
int i=lo;
int j=min+1;   
int k=0;   

int *b=new int[hi-lo+1];   

while(i<=min && j<=hi)
{
if(jkj[i]<jkj[j])   
b[k++]=jkj[i++];
else
b[k++]=jkj[j++];
}

while(i<=min)   
b[k++]=jkj[i++];

while(j<=hi)
b[k++]=jkj[j++];

for(i=hi;i>=lo;i--)
jkj[i]=b[--k];

}

void mrgsrt(int *jkj, int lo, int hi)
{
if(lo<hi)
{
int min=((lo+hi)/2);
mrgsrt(jkj,lo,min);
mrgsrt(jkj,min+1,hi);
mrgArray(jkj,lo,min,hi);
}
}

int main()
{

int jkj[]={2,5,4,1,23,34,45,12,68,35,46,15,67};

mrgsrt(jkj,0,12);

for(int i=0;i<13;i++)
{
cout<<jkj[i]<<\" \";
}
  
return 0;
}

Time Complexity: O(n)