Are Linked Lists good for sorting?

The linked list is a very popular data structure that has many applications in the real world. If youre preparing for an interview, as a software engineer or developer, theres a good chance that you might face a problem that requires sorting a linked list. Merge sort is one of the few algorithms which can do this efficiently.

So, if youre preparing for technical interviews, this article is very important for you! We will be covering the following:

• What Is Merge Sort?
• How Does Merge Sort Work on a Linked List?
• Tortoise and Hare Approach
• Algorithm and Explanation
• Pseudocode
• Code
• Output
• Time and Space Complexity
• FAQs

Applying merge sort on a linked list is a little bit trickier than using merge sort on an array. So, we highly recommend you to read this article on merge sort before reading this one.

What Is Merge Sort?

Merge sort is an efficient way of sorting a list of elements. It is a comparison-based sorting algorithm. It belongs to the divide-and-conquer paradigm, wherein we divide the problem into subproblems, solve them individually, and combine their solutions to form the solution to the original problem.

How Does Merge Sort Work on a Linked List?

It works on a linked list in the same way it works on an array. It recursively divides the list into two parts until we have sublists of size one. Then we combine them in a manner so that they give a sorted list.

Merge sort works on an array in the following manner:

In this article, for a linked list containing N nodes, we will use the term middle position to denote the ceil[N/2]th position [considering 1-based indexing]. Here are a couple of examples:

• Odd number of elements: If the number of elements is five, we will consider the ceil[5/2]th element [the third element] to be the middle element
• Even number of elements: If the list has four elements, we will consider ceil[4/2]th element [the second element] to be the middle element.

As we can see, in a list of size N, we split the list at the middle position.

Unlike an array, the linked list does not support random access. It only supports sequential access. This means, in an array, we can access any element in O[1]. However, to access any element in a linked list, we need to linearly iterate over the entire linked list. Therefore, the time required is O[i] to access the ith element of the linked list.

A linked list data structure is used mainly when the size of the data is unknown or dynamic. We only know the head pointer and the fact that the last element in the linked list will be pointing to NULL. These limitations make it difficult to find the middle point of the linked list. However, there exists a method known as the Tortoise and Hare Approach to do this.

Tortoise and Hare Approach

In this method, we take two pointers:

• Slow: Pointing to the first element of the list
• Fast: Pointing to the second element of the list

If theres only one element in the list, the second pointer will point to the null pointer.

At each step, we move the slow pointer by one step and the fast pointer by two steps. In doing so, when the fast pointer either reaches the last element of the linked list or it points to a null pointer, the slow pointer would have reached the middle of the list.

More precisely, in an odd-length linked list, the fast pointer reaches the null pointer whereas, in an even-length linked list, the fast pointer reaches the last element at the same iteration when the slow pointer reaches the middle element.

See the following figures to visualize it. Initially, the slow pointer is at the beginning, and the fast pointer is at the second element.

The slow pointer moves by 1 and reaches 2; the fast pointer moves by 2 and reaches 4.

Again, the slow pointer moves by 1 and reaches 3; the fast pointer moves by 2 and reaches the null pointer.

As you can see, when the fast pointer reaches the null pointer, the slow pointer reaches the middle of the linked list. If we have a linked list containing an even number of elements, the slow pointer will be at the middle element when the fast pointer is at the last element.

Algorithm for Sorting a Linked List Using Merge Sort

The algorithm is the same as merge sorting an array.

Step 1: Dividing the Lists Into Two Smaller Sublists

We will keep on recursively dividing the lists into two smaller sublists until the size of each sublist becomes 1. We will calculate the middle point of the linked list using the tortoise and hare approach, as explained above.

Have a look at the following figure to see how a linked list gets broken down.

Step 2: Merging the Sublists to Produce a Sorted List

In this step, we merge the linked list similarly as we used to merge them in an array.

Lets assume the two sorted lists are A: [1, 4, 5, 6] and B: [2, 3, 8, 7], and we are storing the merged and sorted linked list in C. The image below shows a few steps on how we merge two sorted linked lists. The rest of the steps are the same as that of merging two sorted arrays.

The linked list comes with a disadvantage: that it couldn't be randomly accessed. On the other hand, it gives us the flexibility to remove the head from a linked list in O[1] complexity. Also, adding an element at the end of the linked list is also O[1].

So, while merging, we dont need an auxiliary array to store the elements in the correct order; instead, we can remove the head node from a list, append it to the end of the sorted list and move the pointer to the next node using next pointer [if possible]. Therefore, by exploiting the next pointer concept, we can achieve O[1] auxiliary memory in merging two sorted lists.

Pseudocode for Sorting a Linked List Using Merge Sort

Here is the pseudocode for the above algorithm. Understand it thoroughly and implement it in any language of your choice.

Function: tortoiseAndHareApproach [Node start]
pointer slow = start
pointer fast = next of start
while[fast is not null and next of fast is not null]
slow = next of slow
fast = next of next of fast
return slow


Function: merge [list A, list B]
list C
pointer ptr_A = beginning of A
pointer ptr_B = beginning of B
pointer ptr_C = beginning of C
while[ptr_A is not equal to end of A and ptr_B is not equal to end of B]
if[ element at ptr_A is less than element art ptr_B]
append element at ptr_A to C
move ptr A to next element in A
else [ element at ptr_B is less than element art ptr_A]
append element at ptr_B to C
move ptr B to next element in B
if [ ptr_A is equal to end of A]
// there may be some elements left in B
while [ptr_B is not equal to end of B]
append element at ptr_B to C
move ptr B to next element in B
else
while [ptr_A is not equal to end of A]
append element at ptr_A to C
move ptr A to next element in A


Function: mergeSort [node st]
if [next of st == null]
return st
pointer ptr_mid = tortoiseAndHareApproach [st]
pointer start_of_right = next of ptr_mid
next of ptr_mid = null
list left_sorted = mergeSort [st]
list right_sorted = mergeSort [start_of_right]
pointer sorted_st = mergeSort [left_sorted, right_sorted]
return sorted_st

Code for Sorting a Linked List Using Merge Sort

We hope you have tried implementing the pseudocode. Here is the implementation for the above algorithm in C++ to sort the array in increasing order.

#include
using namespace std;

struct node
{
int data;
node *next;
node[]
{
data = 0;
next = NULL;
}
};

// Function to print the linked list starting from head pointer
void print[node *head]
{
while [head != NULL]
{
cout data next;
}
cout next;
while [fast != NULL && fast->next != NULL]
{
slow = slow->next;
fast = [fast->next]->next;
}
// slow must be pointing at the middle element of the list
return slow;
}

// Function to take two sorted linked lists and merge them
// to form a sorted resultant linked list
node * merge[node *left, node *right]
{

// creating an auxiliary head node storing the

// the head of the linked list to be returned and

// another pointer to remember where the last

// added node was
node *dummyHead = new node[];
node *current = dummyHead;

while [left != NULL && right != NULL]
{
if [left->data data]
{
current-> next = left;
left = left->next;
current = current-> next;
}
else if [right->data < left->data]
{
current->next = right;
right = right->next;
current = current->next;
}
}
while [left != NULL]
{
current->next = left;
left = left->next;
current = current->next;
}
while [right != NULL]
{
current->next = right;
right = right->next;
current = current->next;
}
return dummyHead->next;
}

// Function to recursively divide the linked list
node * mergeSort[node *start]
{
if [start -> next == NULL]
{
// only 1 element in current list
// so return it as it is
return start;
}
// finding middle of the list using
// the tortoise and hare approach
node *mid = tortoiseAndHareApproach[start];
node *start_of_right = mid->next;

// breaking the linked list into two parts
mid->next = NULL;

node *left = mergeSort[start];
node *right = mergeSort[start_of_right];

node *new_head = merge[left, right];

return new_head;
}


// Function to push a node at the front of linked list
void push[int val, node **ptr_to_head]
{
// create a new node
node *temp = new node[];
// assigning value to be inserted to the new node
temp->data = val;
// making the link between new node and the head of the linked list
temp->next = *ptr_to_head;
// making new node the head of the linked list
*ptr_to_head = temp;
}

// Driver Code
int main[]
{
node* head = NULL;
push[7, &head];

push[8, &head];

push[2, &head];

push[3, &head];

push[6, &head];
push[1, &head];
push[4, &head];
push[5, &head];
cout