Linked List Merge Sort

  2. Tutorial
  3. Data Structure
  4. Linked List Merge Sort
Harshit Jindal Oct 12, 2023
Data Structure Linked List
  1. Linked List Merge Sort Algorithm
  2. Linked List Merge Sort Illustration
  3. Linked List Merge Sort Implementation
  4. Linked List Merge Sort Algorithm Complexity
Linked List Merge Sort

In this tutorial, we will learn how to sort a linked list using the Merge Sort algorithm. It is one of the most preferred algorithms for sorting a linked list because slow random access of pointers makes other algorithms perform poorly( example: quicksort and heapsort).

Linked List Merge Sort Algorithm

Let the head be the first node of the linked list to sort.

mergeSort(head)

  • If the linked list is empty or has 1 node, it is already sorted. Return the linked list as it is.
  • Get the mid node and its previous node prev using the getMid() function.
  • Set prev->next to NULL to break the linked list into two equal parts.
  • Recursively call mergeSort(head) and mergeSort(mid) to sort the two smaller linked lists.
  • Merge the two sorted linked lists using the merge(head, mid) function.

getMid(head)

We take two pointers, one slow and one fast, the fast pointer covers the linked list at twice the speed of slow, and the slow pointer lands at the mid node when the fast node lands at the end of the linked list. We also take a prev node to handle the splitting of linked lists in the MergeSort() function.

  • Initialize mid as head, fast as head, and prev as NULL.
  • While fast!=NULL and fast->next!=NULL, do the following:
    • prev=mid, store reference to the pointer before mid to split lists.
    • mid = mid->next, move mid at a speed of 1 node per iteration.
    • fast = fast->next->next, move fast at a speed 2 times that of mid.
  • return a pair of nodes containing both prev and mid.

merge(F,B)

F is the head of the first part of the linked list, and B is the head of the second part of the linked list. We merge both sorted sublists, F and B, to get the final sorted linked list.

  • Initialize first pointing towards F and second pointing towards B. Also, initialize merged with NULL to hold the merged sorted list and tail to manage the end of the sorted list.
  • While we do not run out of either first or second, do the following:

    • Compare first with second to find the lesser element and initialize insertedNode with it.
      ```c++
      if (first->data < second->data) {
      insertedNode = first;
      first = first->next;
      }

      else {
  `insertedNode` = `second`;
  `second` = `second->next`;
}
```

    • If merged is empty, initialize it with tail.

    • Append insertedNode at the end of tail and move the tail pointer ahead.

      `tail->next` = `insertedNode`
​`tail` = `insertedNode`
  • If there are remaining elements in F do the following:
    • Append first to tail’s end and move tail pointer ahead, tail->next = first, tail = first.
    • Move first one node ahead, first = first->next.
  • If there are remaining elements in S do the following:
    • Append second to tail’s end and move tail pointer ahead, tail->next = second, tail = second.
    • Move second one node ahead, second = second->next.
  • Append NULL to tail’s end and return the merged sorted list.

Linked List Merge Sort Illustration

  • Let’s take the linked list 3 -> 2 -> 4 -> 1 -> NULL
  • We split it into two linked lists 3 -> 2 -> NULL and 4 -> 1 -> Null
  • We split 3 -> 2 -> Null into 3 -> Null and 2 -> Null , Merge them to get sorted sub-list 2 -> 3 -> Null
  • We split 4 -> 1 -> Null into 4 -> Null and 1 -> Null , Merge them to get sorted sub-list 1 -> 4 -> Null
  • Merge 2 -> 3 -> Null and 1 -> 4 -> Null to get the sorted linked list as 1 -> 2 -> 3 -> 4 -> Null.

Linked List Merge Sort Implementation

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node* next;
  Node(int x) {
    this->data = x;
    this->next = NULL;
  }
};

pair<Node*, Node*> getMid(Node* head) {
  Node* mid = head;
  Node* fast = head;
  Node* prev = NULL;

  while (fast != NULL && fast->next != NULL) {
    prev = mid;
    mid = mid->next;
    fast = fast->next->next;
  }

  pair<Node*, Node*> result(prev, mid);
  return result;
}

Node* merge(Node* F, Node* B) {
  Node* first = F;
  Node* second = B;
  Node* merged = NULL;
  Node* tail = NULL;

  while ((first != NULL) && (second != NULL)) {
    Node* insertedNode = NULL;

    if (first->data < second->data) {
      insertedNode = first;
      first = first->next;
    } else {
      insertedNode = second;
      second = second->next;
    }

    if (merged) {
      tail->next = insertedNode;
      tail = insertedNode;
    } else {
      merged = tail = insertedNode;
    }
  }
  while (first != NULL) {
    tail->next = first;
    tail = first;
    first = first->next;
  }

  while (second != NULL) {
    tail->next = second;
    tail = second;
    second = second->next;
  }
  if (tail) {
    tail->next = NULL;
  }

  return merged;
}

void mergeSort(Node*& head) {
  if ((head == NULL) || (head->next == NULL)) {
    return;
  }
  pair<Node*, Node*> a = getMid(head);
  Node* prev = a.first;
  Node* mid = a.second;

  if (prev) {
    prev->next = NULL;
  }

  mergeSort(head);
  mergeSort(mid);
  head = merge(head, mid);
}

void printList(Node* head) {
  Node* curr = head;
  while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->next;
  }
  cout << "\n";
}

int main() {
  Node* head = new Node(5);
  head->next = new Node(6);
  head->next->next = new Node(4);
  head->next->next->next = new Node(3);
  head->next->next->next->next = new Node(2);
  head->next->next->next->next->next = new Node(1);
  printList(head);
  mergeSort(head);
  printList(head);
  return 0;
}

Linked List Merge Sort Algorithm Complexity

Time Complexity

  • Average Case

Merge sort is a recursive algorithm. The following recurrence relation gives the time complexity expression for Merge sort.

T(n) = 2T(n/2) + θ(n)

This result of this recurrence relation gives T(n) = nLogn. We can also see it as a linked list of size n being divided into a maximum of Logn parts. Sorting each part and merging each of them takes O(n) time.

Hence the time complexity is of the order of [Big Theta]: O(nlogn).

  • Worst Case

The worst-case time complexity is [Big O]: O(nlogn). It is the same as average-case time complexity.

  • Best Case

The best-case time complexity is [Big Omega]: O(nlogn). It is the same as the worst-case time complexity. But if the linked list is already sorted, we can reduce the time complexity to O(n).

Space Complexity

The space Complexity for the Merge Sort algorithm on the linked list is O(logn) due to the space occupied by the recursive calls in the stack. If we ignore the space taken by recursive calls, the space complexity can be considered as O(1).

Author: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Related Article - Data Structure

Related Article - Linked List