Merge sort using Linked List

struct node
{
    int data;
    struct node* next;
};
  
void MergeSort(struct node** headRef)
{
  struct node* head = *headRef;
  struct node* a;
  struct node* b;
   if ((head == NULL) || (head->next == NULL)){
    return;
  }
  FrontBackSplit(head, &a, &b); 
  MergeSort(&a);
  MergeSort(&b);
  *headRef = SortedMerge(a, b);
}
 
struct node* SortedMerge(struct node* a, struct node* b)
{
  struct node* result = NULL;
 
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);

  if (a->data <= b->data){
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}
 
/* Split the nodes of the given list into front and back halves.
     If the length is odd, the extra node should go in the front list. */
void FrontBackSplit(struct node* source, struct node** frontRef, 
                    struct node** backRef){
  struct node* fast;
  struct node* slow;

  if (source==NULL || source->next==NULL) {
    *frontRef = source;
    *backRef = NULL;
  }
  else {
    slow = source;
    fast = source->next;
 
    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL)
    {
      fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }
 
    /* 'slow' is before the midpoint in the list, so split it in two
      at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
  }
}

Leave a comment