Table of contents

Introduction

Bubble Sort

2.1.

Approach

2.2.

Program

2.3.

Complexities

Merge Sort

3.1.

Approach

3.2.

Algorithm / Pseudo Code

3.3.

Program

3.4.

Complexities

Frequently Asked Questions

4.1.

What are divide and conquer algorithms?

4.2.

What is the best sorting algorithm for a large dataset?

Conclusion

Last Updated: Mar 27, 2024

Easy

Sort a Linked List

Author Husen Kagdi

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

The linked list is one of the most essential and fundamental data structures which is widely used. It is a linear data structure and is heavily used in implementing operating systems. Sorting is an important application, and we must learn how to sort a linked list. Let us look at how to perform bubble sort and merge sort on a linked list.

Bubble Sort

Approach

Bubble Sort is one of the most popular and naive sorting algorithms. In this technique, we find the maximum element from the unsorted part and place it at its correct position, at the end of the unsorted part. We repeatedly do it for every element.

So in case of sorting a linked list, for each element, we traverse through the entire unsorted part of the linked list. Initially, the entire array is unsorted, and gradually we sort it by increasing its size in every iteration.

Program

#include <iostream>
using namespace std;
 
// Linked list node class.
class Node
{
public:
    int data;
    Node *next;
 
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
 
// Function to sort the linked list.
Node *bubbleSort(Node *head)
{
    Node *temp1 = head, *temp2;
    while (temp1 != NULL)
    {
        temp2 = head;
 
        // Finding the largest element in the unsorted part.
        // We put it at the end of the unsorted part.
        while (temp2->next != NULL)
        {
            if (temp2->data > temp2->next->data)
            {
                int temp = temp2->data;
                temp2->data = temp2->next->data;
                temp2->next->data = temp;
            }
            temp2 = temp2->next;
        }
        temp1 = temp1->next;
    }
    return head;
}
 
// Function to take user input and create the linked list.
Node *takeinput()
{
    int data;
    cin >> data;
    Node *head = NULL, *tail = NULL;
    while (data != -1)
    {
        Node *newnode = new Node(data);
        if (head == NULL)
        {
            head = newnode;
            tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
        cin >> data;
    }
    return head;
}
 
// Function to print the linked list.
void print(Node *head)
{
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}
 
int main()
{
    // Taking user input. (ELements before -1 are considered to be data of the linked list).
    Node *head = takeinput();
   
    // Calling 'bubbleSort()' function to sort the linked list.
    head = bubbleSort(head);
 
    // Printing the linked list.
    print(head);
}

You can also try this code with Online C++ Compiler

Run Code

Input

5 4 3 2 1 -1

Output

1 2 3 4 5

Complexities

Time Complexity

O(N * N), ‘N’ is the size of the linked list.

The bubble sort uses two nested loops to sort an array. In each iteration, the largest element gets placed in the right position. Each iteration takes O(N) time in the worst case. Thus overall, it takes O(N * N) time.

T(N) = i=1n-1i

Space Complexity

O(1)We declare only a few variables. Thus the space complexity is constant.

Merge Sort

Approach

MergeSort is a Divide and conquer technique to sort elements in either increasing or decreasing order. In this technique, we repeatedly divide the linked list into almost two halves. We recursively divide them until they boil down to a single element. Since an array of one size is already sorted, we start merging them until they are to their original size. We use the Merge technique for merging, which is the heart of the Merge sort algorithm. Have a look at the below example to understand the internal details.

Divide Step

Merge Step

Algorithm / Pseudo Code

Merge Sort utilizes the divide and conquer strategy.

Here, we divide the linked list into two halves and repeat the process recursively up until it hits the base case. The base occurs when the size of the list is one. Each list of size one is already sorted.
Now, we keep on building our sorted list by merge procedure. The merge procedure takes two sorted linked lists of size X and Y respectively and merges them to form a linked list of size X + Y which is also sorted.
We repeat the process recursively up until the size of the linked list becomes N, that is the size of the original list.
Finally, our linked list gets sorted.

Program

#include <iostream>
using namespace std;
 
// Linked list node class.
class Node
{
public:
    int data;
    Node *next;
 
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
 
// Function to find the middle node of the linked list.
Node *findmid(Node *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
 
    Node *slow = head;
    Node *fast = head->next;
 
    // If the fast pointer reaches end, then the slow pointer reaches the middle.
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
 
// Function to merge two sorted linked lists.
Node *mergeTwoSortedLinkedLists(Node *head1, Node *head2)
{
    // If one linked list is NULL, returning the head pointer of another linked list.
    if (head1 == NULL)
    {
        return head2;
    }
    if (head2 == NULL)
    {
        return head1;
    }
 
    Node *fh = NULL, *ft = NULL;
    if (head1->data < head2->data)
    {
        fh = head1;
        ft = head1;
        head1 = head1->next;
    }
    else
    {
        fh = head2;
        ft = head2;
        head2 = head2->next;
    }
 
    // Merging two sorted small linked list.
    while (head1 != NULL && head2 != NULL)
    {
        if (head1->data < head2->data)
        {
            ft->next = head1;
            ft = ft->next;
            head1 = head1->next;
        }
        else
        {
            ft->next = head2;
            ft = ft->next;
            head2 = head2->next;
        }
    }
 
    // Attaching linked list 2 at the end, if linked list 1's size is 0.
    if (head1 == NULL)
    {
        ft->next = head2;
    }
 
    // Attaching linked list 1 at the end if linked list 2's size is 0.
    else
    {
        ft->next = head1;
    }
 
    return fh;
}
 
// Merge Sort Function.
Node *mergeSort(Node *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
 
    // Finding the middle node.
    Node *mid = findmid(head);
 
    // Split the linked list across middle node.
    Node *head2 = mid->next;
    mid->next = NULL;
   
    // Divide step.
    Node *temp1 = mergeSort(head);
    Node *temp2 = mergeSort(head2);
 
    // Merge step.
    Node *ans = mergeTwoSortedLinkedLists(temp1, temp2);
    return ans;
}
 
// Function to take user input and create the linked list.
Node *takeinput()
{
    int data;
    cin >> data;
    Node *head = NULL, *tail = NULL;
    while (data != -1)
    {
        Node *newnode = new Node(data);
        if (head == NULL)
        {
            head = newnode;
            tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
        cin >> data;
    }
    return head;
}
 
// Function to print the linked list.
void print(Node *head)
{
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}
 
int main()
{
    // Taking user input. (ELements before -1 are considered to be data of the linked list).
    Node *head = takeinput();
 
    // Calling 'mergeSort()' function to sort the linked list.
    head = mergeSort(head);
 
    // Printing the linked list.
    print(head);
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

5 4 3 2 1 -1

Output

1 2 3 4 5

Complexities

Time Complexity

O(N * log(N)), where ‘N’ is the size of the linked list.

The merge sort is a divide and conquer algorithm which divides the linked list into exactly two halves at every step. Thus the problem gets divided into two smaller subproblems of equal size. Therefore if we divide the array into two halves at every step, it takes O(log(N)) time to reduce the linked list to an element. The merge step merges two sorted sublists of almost equal size into a large linked list. It takes O(N) time to merge.

Recurrence Relation: T(N) = 2 * T(N / 2) + O(N)

Solving it, we get O(N * log(N)) time complexity.

Space Complexity

O(N), where ‘N’ is the size of the linked list.

In the merge step, we take an auxiliary list of size ‘N’ to merge the sublists. The recursion stack takes O(log(N)) space. Thus overall, it takes O(N) time.

Frequently Asked Questions

What are divide and conquer algorithms?

Divide and Conquer algorithms divide the problem into multiple subproblems and then combine the results to present the result of the original problem as a whole after the required processing

What is the best sorting algorithm for a large dataset?

Merge sort is the best sorting algorithm for a large dataset as it has the worst case time complexity of O(N*logN) where N is the size of the dataset.

Conclusion

In this blog, we learned about LinkedList and how to apply sorting techniques to them. We learned about bubble sort, which took O(N * N) time, and then we learned about merge sort, which took O(N * log(N)) time. Stay tuned to learn more about these essential data structures.