Merge Sort a singly Linked List

Merge sort is a fast comparison based sorting algorithm which can be utilized in sorting a Linked List as well. Merge Sort is preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms such as Quick Sort perform poorly, and others such as Heap Sort completely impossible.


Algorithm


The algorithm is same as that of Merge Sort will implementation changes to accomodate the structure of Linked List.

merge sort a linked list

Pseudocode



Merge_Sort(head_reference)

STEP 1: If head is NULL or there is only one element in the Linked List 
    then return the Linked List
    
STEP 2: Divide the linked list into two equal halves.  
      Split_Linked_List(head, &first_half, &second_half);
      
STEP 3: Sort the two halves first_half and second_half.
      MergeSort(first_half);
      MergeSort(second_half);
      
STEP 4: Merge the sorted first_half and second_half (using Merge_Sort() recursively) 
   and update the head pointer using head_reference.
     *head_reference = Merge_Sort(first_half, second_half);

Complexity


  • Worst case time complexity: Θ(N log N)
  • Average case time complexity: Θ(N log N)
  • Best case time complexity: Θ(N log N)
  • Space complexity: Θ(1)

Implementations


Implementation of applying Merge Sort on a Linked List is as follows:

  • C
  • Java

C


#include<stdio.h>
#include<stdlib.h>
struct Node
{
      int data;
      struct Node* next;
};
struct Node* SortedMerge(struct Node* a, struct Node* b);
void FrontBackSplit(struct Node* source, struct Node** frontRef, struct Node** backRef);
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);
}
void FrontBackSplit(struct Node* source, struct Node** frontRef, struct Node** backRef)
{
    struct Node* fast;
    struct Node* slow;
    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 push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);  
    (*head_ref) = new_node;
} 
int main()
{
    struct Node* res = NULL;
    struct Node* a = NULL;
    push(&a, 3);
    push(&a, 1);
    push(&a, 2);
    MergeSort(&a);
    getchar();
    return 0;
}

Java


public class linkedList 
{
    node head = null;
    static class node 
    {
        int val;
        node next;
    public node(int val) 
    {
        this.val = val;
    }
}

node sortedMerge(node a, node b) 
{
    node result = null;
    if (a == null)
        return b;
    if (b == null)
        return a;

    if (a.val &lt;= b.val) 
    {
        result = a;
        result.next = sortedMerge(a.next, b);
    } 
    else
    {
        result = b;
        result.next = sortedMerge(a, b.next);
    }
    return result;

}

node mergeSort(node h) 
{
    if (h == null || h.next == null)
    {
        return h;
    }

    node middle = getMiddle(h);
    node nextofmiddle = middle.next;

    middle.next = null;

    node left = mergeSort(h);

    node right = mergeSort(nextofmiddle);

    node sortedlist = sortedMerge(left, right);
    return sortedlist;
}

node getMiddle(node h) 
{
    //Base case
    if (h == null)
        return h;
    node fastptr = h.next;
    node slowptr = h;
    
    while (fastptr != null)
    {
        fastptr = fastptr.next;
        if(fastptr!=null)
        {
            slowptr = slowptr.next;
            fastptr=fastptr.next;
        }
    }
    return slowptr;
}

void push(int new_data) 
{
    node new_node = new node(new_data);
    new_node.next = head;
    head = new_node;
}

public static void main(String[] args) 
{

    linkedList li = new linkedList();
    li.push(3);
    li.push(2);
    li.push(1);

    li.head = li.mergeSort(li.head);
}

}


Questions


What is the time complexity of this algorithm if Linked List is already sorted?

O(N)
O(1)
O(N log N)
O(log N)