JIYIK CN >

In this article, we will learn how to sort a linked list using merge sort algorithm. It is one of the most preferred algorithms to sort a linked list because slow pointer random access makes the performance of other algorithms worse (for example: quicksort and heapsort).

Linked list merge sort algorithm

Let headbe the first node of the linked list to be sorted.

mergeSort(head)

• If the linked list is empty or the node is 1, then the list is already sorted. Return the linked list as is.
• Use getMid()the function to get midthe node and its previous node prev.
• Setting prev->nextto NULLdivides the linked list into two equal parts.
• Recursively call mergeSort(head)and mergeSort(mid)to sort the two smaller linked lists.
• Use merge(head, mid)the function to merge two sorted linked lists.

getMid(head)

We use two pointers, one for slowand the other for fast. The fastpointer slowcovers the linked list at twice the speed of , and when fastthe node falls at the end of the linked list, slowthe pointer falls on midthe node. We also use a prevnode to handle MergeSort()the splitting of the linked list in the function.

• Initialize midto head, fastinitialize to head, and previnitialize to NULL.
• At the same time as fast!= NULLand fast->next!= NULL, do the following:
  • prev= mid, stores a reference to the pointer before the midpoint to the split list.
  • mid= mid->next, each iteration 1moves to the middle at a speed of nodes.
  • fast= fast->next->next, moves at twice the speed fastof .mid
• Returns a pair of nodes consisting of prevand mid.

merge(F,B)

Fis the beginning of the first part of the linked list, and Bis the beginning of the second part of the linked list. We merge the two sorted sublists F and B to obtain the final sorted linked list.

• Initializes to point to Fand firstto point to B. secondSimilarly, NULLinitializes mergedto hold the merged sorted list and uses tailto manage the end of the sorted list.

• While we haven't run out of firstor second, do the following:

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

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

  • If mergedis empty, tailit is initialized with .

  • Appends to the end of tail insertedNodeand tailmoves the pointer forward.

Linked list merge sort diagram

• Let's look at the linked list3 -> 2 -> 4 -> 1 -> NULL
• We split it into two linked lists: 3 -> 2 -> NULLand4-> 1->空
• We 3 -> 2 -> Nullsplit into 3 -> Nulland 2 -> Null, merge them to get the sorted sublists2 -> 3 -> Null
• We 4 -> 1 -> Nullsplit into 4 -> Nulland 1 -> Nulland merge them to get the sorted sublists1 -> 4 -> Null
• Merge 2 -> 3 -> Nulland 1 -> 4 -> Nullto get the sorted linked list of 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;
}

Complexity of linked list merge sort algorithm

Time Complexity

• Average situation

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

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

The result of this recurrence relation is T(n) = nLogn. We can also view it as na linked list of size , which is partitioned into at most Lognparts. Sorting each part and merging each part takes O(n)time.

Therefore, the time complexity is about [big Theta]: O(nlogn).

• Worst case scenario

The worst case time complexity is [Big O]: O(nlogn). It is the same as the 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. However, if the linked list is sorted, the time complexity can be reduced to O(n).

Space complexity

Due to the space occupied by recursive calls in the stack, the space complexity of the merge sort algorithm on the linked list is O(logn). If we ignore the space occupied by recursive calls, the space complexity can be considered as O(1).