October 7, 2024

Merge Sort for Linked Lists

Problem Statement

Given a singly linked list, use the merge sort algorithm to sort the list in the ascending order of their node’s values.

Example

Input

4 --> 3 --> 2 --> 5 --> 1 --> null

Output

1 --> 2 --> 3 --> 4 --> 5 --> null

Example Explanation

The nodes in the input are not arranged in any particular order, while they are arranged in ascending order of their value in the output.

Constraints

$0 < n < 10^5,$ where $n$ is the number of nodes.
$-10^9 < \text{node.val} < 10^9$

Algorithm 1

Merge sort for linked lists is preferred to sort linked lists because accessing a random node in a linked list is a costly operation which makes other algorithms like quicksort, heapsort, etc inefficient.

The algorithm of merge sort for linked lists is quite similar to sorting an array using merge sort. We will be having a recursive function mergeSort which divides the list into two halves and recurse back for the left and the right half. After that, we will have another function mergeSorted which will be used to merge the sorted parts.

The steps required in the algorithm are as follows –
mergeSort(head) –

Let the function be mergeSort that accepts a single argument head which denotes the pointer to the head of the linked list.
In the function, firstly we will check if the head itself is null or if the list with its head node as head consists of only one node. If any of the above conditions is found to be true, we will simply return head.
Now we will find the middle node of the liked list whose head node is head, let it be mid.
Now we will divide the list into two halves, therefore we will remove the next link of the mid node $i.e.$ mid.next = null.
Recur for the left and right half of the partitioned list, let the node returned by them be left and right respectively.
Call the mergeSorted function to merge the sorted left part and the sorted right part. Let after merging two individually sorted parts, the head node of the combined linked list is answer.
Return the answer node which represents the head of the sorted linked list.

The steps required to merge the sorted parts are as follows –
mergeSorted(left, right) –

Let the function mergeSorted accepts two arguments of node type left and right denoting the head of two independent sorted lists.
Now we will have some base conditions –
- If left is null then return right.
- Else if right is null then return left.
Then we will declare a node type variable res to store the result.
Now we will check if left.val is smaller than or equal to right.val, then we will assign left to res and recurse for the left.next and assign the obtained result to res.next.
Now we will check if left.val is greater than right.val, then we will assign right to res and recurse for the right.next and assign the obtained result to res.next.
At last we will return the res as our answer.

Java Implementation

// Java program to sort a linked list
// using the merge sort algorithm.
public class Main{
    // Node class
    static class Node{
        int val;
        // Pointer to its next node
        Node next;

        // Constructor
        Node(int val){
            this.val = val;
        }
    }

    // Function to print the list
    static void printList(Node head){
        // Iterating while head is not null.
        while (head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }

        System.out.println();
    }

    // Function to find the middle 
    // node of the linked list.
    static Node findMiddle(Node head){
        // Base condition.
        if (head == null)
            return head;

        // Slow and fast pointers to 
        // iterate over the list.
        // Fast pointer will take 2 steps
        // at a time while slow pointer will
        // take 1 step at a time.
        Node slow = head, fast = head;

        // Iterating while we have reached 
        // last or second last node of the list.
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // Node pointed by the slow pointer is the middle
        // node of the list.
        return slow;
    }

    // Function to merge two already sorted lists.
    static Node mergeSorted(Node left, Node right){
        // Base cases to check if either of
        // the list provided is empty.
        if (left == null)
            return right;
        if (right == null)
            return left;

        // Declaring the variable 'res' to hold
        // the result.
        Node res = null;

        // If left's val is smaller than or equal
        // to right's val.
        if (left.val <= right.val){
            // Assigning left to res.
            res = left;

            // Recurring for left.next and 
            // assigning answer to res.next.
            res.next = mergeSorted(left.next, right);

        }

        // Otherwise left's val is greater than
        // right's val.
        else {
            // Assigning right to res.
            res = right;

            // Recurring for right.next and 
            // assigning answer to res.next.
            res.next = mergeSorted(left, right.next);

        }

        // Returning the result.
        return res;
    }
    // Function to sort the list.
    static Node mergeSort(Node head){
        // Base condition to check if the head
        // itself is null or the list consists of 
        // only a single node. 
        if (head == null || head.next == null){
            return head;
        }

        // Finding the middle node of the list.
        Node mid = findMiddle(head);

        // Finding the next node of the middle node.
        Node nextToMid = mid.next;

        // Breaking the list into two halves.
        mid.next = null;

        // Recurring for the left and the right
        // halves obtained.
        Node left = mergeSort(head);
        Node right = mergeSort(nextToMid);

        // Merging the already sorted left 
        // and right part of the linked list.
        Node res = mergeSorted(left, right);

        // Returning the result.
        return res;
    }
    public static void main(String args[]){
        // Constructing the following linked list.
        // 4 --> 3 --> 2 --> 5 --> 1 --> null
        Node head = new Node(4);
        head.next = new Node(3);
        head.next.next = new Node(2);
        head.next.next.next = new Node(5);
        head.next.next.next.next = new Node(1);

        // Printing the list before sorting.
        System.out.println("List before sorting - ");
        printList(head);

        // Calling the function to sort the list.
        head = mergeSort(head);

        // Printing the list after sorting. 
        System.out.println("List after sorting -");
        printList(head);
    }
}

Output –

List before sorting - 
4 3 2 5 1 
List after sorting -
1 2 3 4 5

C++ Implementation

// C++ program to sort a linked list
// using the merge sort algorithm.
#include<bits/stdc++.h>
using namespace std;

// Node class
class Node{
public:
    int val;
    // Pointer to its next node
    Node *next;

    // Constructor
    Node(int Val){
        val = Val;
    }
};

// Function to print the list
void printList(Node *head){
    // Iterating while head is not nullptr.
    while (head != nullptr){
        cout << head->val << " ";
        head = head->next;
    }

    cout << endl;
}

// Function to find the middle 
// node of the linked list.
Node *findMiddle(Node *head){
    // Base condition.
    if (head == nullptr)
        return head;

    // Slow and fast pointers to 
    // iterate over the list.
    // Fast pointer will take 2 steps
    // at a time while slow pointer will
    // take 1 step at a time.
    Node *slow = head, *fast = head;

    // Iterating while we have reached 
    // last or second last node of the list.
    while (fast->next != nullptr && fast->next->next != nullptr){
        fast = fast->next->next;
        slow = slow->next;
    }

    // Node pointed by the slow pointer is the middle
    // node of the list.
    return slow;
}

// Function to merge two already sorted lists.
Node *mergeSorted(Node *left, Node *right){
    // Base cases to check if either of
    // the list provided is empty.
    if (left == nullptr)
        return right;
    if (right == nullptr)
        return left;

    // Declaring the variable 'res' to hold
    // the result.
    Node *res = nullptr;

    // If left's val is smaller than or equal
    // to right's val.
    if (left->val <= right->val){
        // Assigning left to res->
        res = left;

        // Recurring for left->next and 
        // assigning answer to res->next->
        res->next = mergeSorted(left->next, right);

    }

    // Otherwise left's val is greater than
    // right's val.
    else {
        // Assigning right to res->
        res = right;

        // Recurring for right->next and 
        // assigning answer to res->next->
        res->next = mergeSorted(left, right->next);

    }

    // Returning the result.
    return res;
}
// Function to sort the list.
Node *mergeSort(Node *head){
    // Base condition to check if the head
    // itself is nullptr or the list consists of 
    // only a single node. 
    if (head == nullptr || head->next == nullptr){
        return head;
    }

    // Finding the middle node of the list.
    Node *mid = findMiddle(head);

    // Finding the next node of the middle node.
    Node *nextToMid = mid->next;

    // Breaking the list into two halves.
    mid->next = nullptr;

    // Recurring for the left and the right
    // halves obtained.
    Node *left = mergeSort(head);
    Node *right = mergeSort(nextToMid);

    // Merging the already sorted left 
    // and right part of the linked list.
    Node *res = mergeSorted(left, right);

    // Returning the result.
    return res;
}
int main(){
    // Constructing the following linked list.
    // 4 --> 3 --> 2 --> 5 --> 1 --> nullptr
    Node *head = new Node(4);
    head->next = new Node(3);
    head->next->next = new Node(2);
    head->next->next->next = new Node(5);
    head->next->next->next->next = new Node(1);

    // Printing the list before sorting.
    cout << "List before sorting - " << endl;
    printList(head);

    // Calling the function to sort the list.
    head = mergeSort(head);

    // Printing the list after sorting. 
    cout << "List after sorting -" << endl;
    printList(head);

    return 0;
}

Output –

List before sorting - 
4 3 2 5 1 
List after sorting -
1 2 3 4 5

Python Implementation

# Python program to sort a linked list
# using the merge sort algorithm.

class Node:
    # Constructor
    def __init__(self, val):
        self.val = val
        self.next = None

# Function to print the list
def printList(head):
    # Iterating while head is not None.
    while (head != None):
        print(head.val, end = " ")
        head = head.next

    print()

# Function to find the middle 
# node of the linked list.
def findMiddle(head):
    # Base condition.
    if (head == None):
        return head

    # Slow and fast pointers to 
    # iterate over the list.
    # Fast pointer will take 2 steps
    # at a time while slow pointer will
    # take 1 step at a time.
    slow, fast = head, head

    # Iterating while we have reached 
    # last or second last node of the list.
    while (fast.next != None and fast.next.next != None):
        fast = fast.next.next
        slow = slow.next


    # Node pointed by the slow pointer is the middle
    # node of the list.
    return slow


# Function to merge two already sorted lists.
def mergeSorted(left, right):
    # Base cases to check if either of
    # the list provided is empty.
    if (left == None):
        return right
    if (right == None):
        return left

    # Declaring the variable 'res' to hold
    # the result.
    res = None

    # If left's val is smaller than or equal
    # to right's val.
    if (left.val <= right.val):
        # Assigning left to res.
        res = left

        # Recurring for left.next and 
        # assigning answer to res.next.
        res.next = mergeSorted(left.next, right)

    # Otherwise left's val is greater than
    # right's val.
    else:
        # Assigning right to res.
        res = right

        # Recurring for right.next and 
        # assigning answer to res.next.
        res.next = mergeSorted(left, right.next)



    # Returning the result.
    return res

# Function to sort the list.
def mergeSort(head):
    # Base condition to check if the head
    # itself is None or the list consists of 
    # only a single node. 
    if (head == None or head.next == None):
        return head


    # Finding the middle node of the list.
    mid = findMiddle(head)

    # Finding the next node of the middle node.
    nextToMid = mid.next

    # Breaking the list into two halves.
    mid.next = None

    # Recurring for the left and the right
    # halves obtained.
    left = mergeSort(head)
    right = mergeSort(nextToMid)

    # Merging the already sorted left 
    # and right part of the linked list.
    res = mergeSorted(left, right)

    # Returning the result.
    return res


# Constructing the following linked list.
# 4 --> 3 --> 2 --> 5 --> 1 --> None
head = Node(4)
head.next = Node(3)
head.next.next = Node(2)
head.next.next.next = Node(5)
head.next.next.next.next = Node(1)

# Printing the list before sorting.
print("List before sorting - ")
printList(head)

# Calling the function to sort the list.
head = mergeSort(head)

# Printing the list after sorting. 
print("List after sorting -")
printList(head)

Output –

List before sorting - 
4 3 2 5 1 
List after sorting -
1 2 3 4 5

Complexity Analysis

Time Complexity – At each iteration, we are dividing the list into two halves and in each step, we are merging the divided parts. Since the merging step requires $O(n)$ time and there are $O(\log_2{n}$] iterations, therefore, the overall time complexity is $O(n\log_2{n})$.
Space Complexity – Since both of the used functions (mergeSort and mergeSorted) are recursive in nature they will require $O(\log_2{n})$ and $O(n)$ recursive stack space respectively. Hence, the overall space complexity is $O(n)$.

Approach 2

In our last algorithm, we have seen how to use merge sort for linked lists. In this approach, we will be seeing the same concept again and will try to reduce the space complexity of the algorithm.
Last time we implemented mergeSorted() function in a recursive manner which is why it required $O(n)$ recursive stack space. But this time we will try to optimize it such that mergeSorted() function will require constant extra space.

The algorithm of the mergeSort() function is the same as in the previous section, hence we are not including it again. However, the mergeSorted() algorithm is now changed and is as follows –
mergeSorted(left, right)

Let the arguments accepted by the mergeSorted() function be nothing but the heads of already sorted linked lists.
As part of our base condition we will be checking if any of the lists is empty.
Then we will declare a node type variable dummy with value 1 and another node type variable node that will point to dummy. The dummy will help to return the answer at the end of the function and the node is required to traverse the list.
Now we will use a while loop to traverse until either of the left or rightpointer does not point to null and do the following –
- If left’s val is smaller than or equal to right’s val then –
  - Assign left to node.next.
  - Move left to its next pointer.
- Otherwise, left’s val is greater than right’s val –
  - Assign right to node.next.
  - Move right to its next pointer.
- At last move node to its next pointer $i.e.$ node = node.next.
After exiting from loop we will be including the nodes left out in the lists. Therefore, we will iterate until the left pointer does not start pointing to null and do the following –
- Assign left to node.next.
- Move left to its next pointer.
- Move node to its next pointer $i.e.$ node = node.next.
We will repeat the above process for the right list $i.e.$ iterate until the right pointer does not start pointing to null and do the following –
- Assign right to node.next.
- Move right to its next pointer.
- Move node to its next pointer $i.e.$ node = node.next
Now the merging part is done, we just need to return the head of the merged list which is pointed by dummy.next. Therefore, we will simply return dummy.next.

Java Implementation

// Java program to sort a linked list
// using the merge sort algorithm.
public class Main{
    // Node class
    static class Node{
        int val;
        // Pointer to its next node
        Node next;

        // Constructor
        Node(int val){
            this.val = val;
        }
    }

    // Function to print the list
    static void printList(Node head){
        // Iterating while head is not null.
        while (head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }

        System.out.println();
    }

    // Function to find the middle 
    // node of the linked list.
    static Node findMiddle(Node head){
        // Base condition.
        if (head == null)
            return head;

        // Slow and fast pointers to 
        // iterate over the list.
        // Fast pointer will take 2 steps
        // at a time while slow pointer will
        // take 1 step at a time.
        Node slow = head, fast = head;

        // Iterating while we have reached 
        // last or second last node of the list.
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // Node pointed by the slow pointer is the middle
        // node of the list.
        return slow;
    }

    // Function to merge two already sorted lists.
    static Node mergeSorted(Node left, Node right){
        // Base cases to check if either of
        // the list provided is empty.
        if (left == null)
            return right;
        if (right == null)
            return left;

        // Dummy node to hold the answer.
        Node dummy = new Node(-1);
        // Declaring another variable 'node'
        // to iterate further
        Node node = dummy;

        // Iterating while both pointers
        // are not null
        while (left != null && right != null){
            // If left's val is smaller than or 
            // equal to right's val.
            if (left.val <= right.val){
                // Assign left to node's next.
                node.next = left;

                // Move left to its next node.
                left = left.next;
            }
            // Otherwise left's val is greater 
            // than right's val. 
            else{
                // Assign right to node's next. 
                node.next = right;

                // Move right to its next.
                right = right.next;
            }
            // Moving node to its next node. 
            node = node.next;
        }

        // Iterating while left is not null.
        while (left != null){
            // Assign left to node's next.
            node.next = left;

            // Move left to its next node.
            left = left.next;

            // Moving node to its next node. 
            node = node.next;
        }

        // Iterating while right is not null.
        while (right != null){
            // Assign right to node's next. 
            node.next = right;

            // Move right to its next.
            right = right.next;

            // Moving node to its next node. 
            node = node.next;
        }

        // Returning dummy's next as our answer.
        return dummy.next;
    }
    // Function to sort the list.
    static Node mergeSort(Node head){
        // Base condition to check if the head
        // itself is null or the list consists of 
        // only a single node. 
        if (head == null || head.next == null){
            return head;
        }

        // Finding the middle node of the list.
        Node mid = findMiddle(head);

        // Finding the next node of the middle node.
        Node nextToMid = mid.next;

        // Breaking the list into two halves.
        mid.next = null;

        // Recurring for the left and the right
        // halves obtained.
        Node left = mergeSort(head);
        Node right = mergeSort(nextToMid);

        // Merging the already sorted left 
        // and right part of the linked list.
        Node res = mergeSorted(left, right);

        // Returning the result.
        return res;
    }
    public static void main(String args[]){
        // Constructing the following linked list.
        // 4 --> 3 --> 2 --> 5 --> 1 --> null
        Node head = new Node(4);
        head.next = new Node(3);
        head.next.next = new Node(2);
        head.next.next.next = new Node(5);
        head.next.next.next.next = new Node(1);

        // Printing the list before sorting.
        System.out.println("List before sorting - ");
        printList(head);

        // Calling the function to sort the list.
        head = mergeSort(head);

        // Printing the list after sorting. 
        System.out.println("List after sorting -");
        printList(head);
    }
}

Output –

List before sorting - 
4 3 2 5 1 
List after sorting -
1 2 3 4 5

C++ Implementation

// C++ program to sort a linked list
// using the merge sort algorithm.
#include<bits/stdc++.h>
using namespace std;

// Node class
class Node{
public:
    int val;
    // Pointer to its next node
    Node *next;

    // Constructor
    Node(int Val){
        val = Val;
    }
};

// Function to print the list
void printList(Node *head){
    // Iterating while head is not nullptr.
    while (head != nullptr){
        cout << head->val << " ";
        head = head->next;
    }

    cout << endl;
}

// Function to find the middle 
// node of the linked list.
Node *findMiddle(Node *head){
    // Base condition.
    if (head == nullptr)
        return head;

    // Slow and fast pointers to 
    // iterate over the list.
    // Fast pointer will take 2 steps
    // at a time while slow pointer will
    // take 1 step at a time.
    Node *slow = head, *fast = head;

    // Iterating while we have reached 
    // last or second last node of the list.
    while (fast->next != nullptr && fast->next->next != nullptr){
        fast = fast->next->next;
        slow = slow->next;
    }

    // Node pointed by the slow pointer is the middle
    // node of the list.
    return slow;
}

// Function to merge two already sorted lists.
Node *mergeSorted(Node *left, Node *right){
    // Base cases to check if either of
    // the list provided is empty.
    if (left == nullptr)
        return right;
    if (right == nullptr)
        return left;

    // Dummy node to hold the answer.
    Node *dummy = new Node(-1);
    // Declaring another variable 'node'
    // to iterate further
    Node *node = dummy;

    // Iterating while both pointers
    // are not null
    while (left != nullptr && right != nullptr){
        // If left's val is smaller than or 
        // equal to right's val.
        if (left->val <= right->val){
            // Assign left to node's next.
            node->next = left;

            // Move left to its next node.
            left = left->next;
        }
        // Otherwise left's val is greater 
        // than right's val. 
        else{
            // Assign right to node's next. 
            node->next = right;

            // Move right to its next.
            right = right->next;
        }
        // Moving node to its next node. 
        node = node->next;
    }

    // Iterating while left is not null.
    while (left != nullptr){
        // Assign left to node's next.
        node->next = left;

        // Move left to its next node.
        left = left->next;

        // Moving node to its next node. 
        node = node->next;
    }

    // Iterating while right is not null.
    while (right != nullptr){
        // Assign right to node's next. 
        node->next = right;

        // Move right to its next.
        right = right->next;

        // Moving node to its next node. 
        node = node->next;
    }

    // Returning dummy's next as our answer.
    return dummy->next;
}
// Function to sort the list.
Node *mergeSort(Node *head){
    // Base condition to check if the head
    // itself is nullptr or the list consists of 
    // only a single node. 
    if (head == nullptr || head->next == nullptr){
        return head;
    }

    // Finding the middle node of the list.
    Node *mid = findMiddle(head);

    // Finding the next node of the middle node.
    Node *nextToMid = mid->next;

    // Breaking the list into two halves.
    mid->next = nullptr;

    // Recurring for the left and the right
    // halves obtained.
    Node *left = mergeSort(head);
    Node *right = mergeSort(nextToMid);

    // Merging the already sorted left 
    // and right part of the linked list.
    Node *res = mergeSorted(left, right);

    // Returning the result.
    return res;
}
int main(){
    // Constructing the following linked list.
    // 4 --> 3 --> 2 --> 5 --> 1 --> nullptr
    Node *head = new Node(4);
    head->next = new Node(3);
    head->next->next = new Node(2);
    head->next->next->next = new Node(5);
    head->next->next->next->next = new Node(1);

    // Printing the list before sorting.
    cout << "List before sorting - " << endl;
    printList(head);

    // Calling the function to sort the list.
    head = mergeSort(head);

    // Printing the list after sorting. 
    cout << "List after sorting -" << endl;
    printList(head);

    return 0;
}

Output –

List before sorting - 
4 3 2 5 1 
List after sorting -
1 2 3 4 5

Python Implementation

# Python program to sort a linked list
# using the merge sort algorithm.

class Node:
    # Constructor
    def __init__(self, val):
        self.val = val
        self.next = None

# Function to print the list
def printList(head):
    # Iterating while head is not None.
    while (head != None):
        print(head.val, end = " ")
        head = head.next

    print()

# Function to find the middle 
# node of the linked list.
def findMiddle(head):
    # Base condition.
    if (head == None):
        return head

    # Slow and fast pointers to 
    # iterate over the list.
    # Fast pointer will take 2 steps
    # at a time while slow pointer will
    # take 1 step at a time.
    slow, fast = head, head

    # Iterating while we have reached 
    # last or second last node of the list.
    while (fast.next != None and fast.next.next != None):
        fast = fast.next.next
        slow = slow.next


    # Node pointed by the slow pointer is the middle
    # node of the list.
    return slow


# Function to merge two already sorted lists.
def mergeSorted(left, right):
    # Base cases to check if either of
    # the list provided is empty.
    if (left == None):
        return right
    if (right == None):
        return left

    # Dummy node to hold the answer.
    dummy = Node(-1)
    # Declaring another variable 'node'
    # to iterate further
    node = dummy

    # Iterating while both pointers
    # are not null
    while (left != None and right != None):
        # If left's val is smaller than or 
        # equal to right's val.
        if (left.val <= right.val):
            # Assign left to node's next.
            node.next = left

            # Move left to its next node.
            left = left.next

        # Otherwise left's val is greater 
        # than right's val. 
        else:
            # Assign right to node's next. 
            node.next = right

            # Move right to its next.
            right = right.next

        # Moving node to its next node. 
        node = node.next


    # Iterating while left is not null.
    while (left != None):
        # Assign left to node's next.
        node.next = left

        # Move left to its next node.
        left = left.next

        # Moving node to its next node. 
        node = node.next


    # Iterating while right is not null.
    while (right != None):
        # Assign right to node's next. 
        node.next = right

        # Move right to its next.
        right = right.next

        # Moving node to its next node. 
        node = node.next


    # Returning dummy's next as our answer.
    return dummy.next

# Function to sort the list.
def mergeSort(head):
    # Base condition to check if head
    # itself is None or list consists of 
    # only a single node. 
    if (head == None or head.next == None):
        return head


    # Finding the middle node of the list.
    mid = findMiddle(head)

    # Finding the next node of the middle node.
    nextToMid = mid.next

    # Breaking the list into two halves.
    mid.next = None

    # Recurring for the left and the right
    # halves obtained.
    left = mergeSort(head)
    right = mergeSort(nextToMid)

    # Merging the already sorted left 
    # and right part of the linked list.
    res = mergeSorted(left, right)

    # Returning the result.
    return res


# Constructing the following linked list.
# 4 --> 3 --> 2 --> 5 --> 1 --> None
head = Node(4)
head.next = Node(3)
head.next.next = Node(2)
head.next.next.next = Node(5)
head.next.next.next.next = Node(1)

# Printing the list before sorting.
print("List before sorting - ")
printList(head)

# Calling the function to sort the list.
head = mergeSort(head)

# Printing the list after sorting. 
print("List after sorting -")
printList(head)

Output –

List before sorting - 
4 3 2 5 1 
List after sorting -
1 2 3 4 5

Complexity Analysis

Time Complexity – Again, at each iteration we are dividing the list into two halves and in each step, we are merging the divided parts. Since the merging step requires $O(n)$ time and there are $O(\log_2{n})$ iterations, therefore, the overall time complexity is $O(n\log_2{n})$.
Space Complexity – Since the mergeSort function is a recursive function that requires $O(\log_2{n})$ recursive stack space, therefore the overall space complexity is $O(\log_2{n})$.

Conclusion

Merge sort is a divide and conquer algorithm whose worst case runtime is $O(n\log_2{n})$, where $n$ is the size of the list/array.
Accessing a random element is an $O(n)$ task in the case of a linked list that is why other efficient algorithms like quicksort, heapsort, etc. perform poorly if applied on a linked list.
Merge sort does not access random elements and hence it wins over other sorting algorithms to sort a linked list.
Merge sort requires $O(n\log_2{n})$ time and $O(\log_2{n})$ space to sort a linked list of $n$ nodes.

FAQ

Q. Why Other Sorting Algorithms are Inefficient on Linked Lists?

A. Let’s try to understand this using an example. For example let the list be –
2 –> 3 –> 1 –> 5 –> 4 –> null

And we have access only to the head node of the list therefore if we use any other algorithm (say quickSort) then we need to access some random elements many times.
Since we have access to the head node only therefore it would require $O(n)$ time just to access nodes.
In other words, it requires $O(1)$ time to access a[k] in an array while to access the $k^{th}$ element of the list it requires $O(k)$ time.

Author

Paras Yadav

View all posts

Merge Sort for Linked Lists

Problem Statement

Example

Input

Output

Example Explanation

Constraints

Algorithm 1

Java Implementation

C++ Implementation

Python Implementation

Complexity Analysis

Approach 2

Java Implementation

C++ Implementation

Python Implementation

Complexity Analysis

Conclusion

FAQ

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Merge Sort for Linked Lists

Problem Statement

Example

Input

Output

Example Explanation

Constraints

Algorithm 1

Java Implementation

C++ Implementation

Python Implementation

Complexity Analysis

Approach 2

Java Implementation

C++ Implementation

Python Implementation

Complexity Analysis

Conclusion

FAQ

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Featured articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?