Kod: Zaznacz cały
void split(struct Node* head,struct Node** front,struct Node** back)
{
struct Node* slow;
struct Node* fast;
if(head==NULL||head->next==NULL)
{
(*front)=head;
(*back)=NULL;
}
else
{
slow=head;
fast=head->next;
while(fast!=NULL)
{
fast=fast->next;
if(fast!=NULL)
{
slow=slow->next;
fast=fast->next;
}
}
(*front)=head;
(*back)=slow->next;
slow->next=NULL;
}
}
void merge(struct Node** head,struct Node* list1,struct Node* list2)
{
struct Node* tmp;
if(list1==NULL) (*head)=list1;
if (list2==NULL) (*head)=list2;
if(list1->data<=list2->data)
{
(*head)=list1;
}else{
(*head)=list2;
list2=list1;
list1=(*head);
}
while((list1->next!=NULL)&&(list2!=NULL))
{
if(list1->next->data<=list2->data){
list1=list1->next;
}else{
tmp=list1->next;
list1->next=list2;
list2=tmp;
}
}
if(list1->next==NULL) list1->next=list2;
}
void mergesort(struct Node** head)
{
struct Node* h1=NULL;
struct Node* h2=NULL;
if((*head)!=NULL&&(*head)->next!=NULL)
{
split((*head),&h1,&h2);
mergesort(&h1);
mergesort(&h2);
merge(head,h1,h2);
}
}
Czy w ten sposób napisana procedura sortuje stabilnie