# Understanding the Algorithm behind Merge Sort for Linked Lists

## What is a Merge Sort?

**Merge sort** is a famous and most optimized sorting algorithm which works on the principle of divide and conquer. It is also known as the divide and conquer algorithm with **time complexity** of **O(n*logn).**

## How does it work?

**Merge sort** works in two easy steps:

- Divide the input list into two sub-lists, each sub-list having the same size.
- Merge the two sub-lists into one big list, and each element in the list is ordered/sorted.

Now, working of **merge sort** for an array can be easily understood, for those who have not any idea on how** merge sort** works for an array can refer to this link

Now, moving on to how **merge sort** works for a linked list, we will first have a look at the **simple approach** of merge sort on a linked list

## Approach:

Step1: Call divideList() and find the mid node of the given linked list and also divide the list into two halvesStep2: Recursively call sortMerge() on both left and right sub-linked list and store the new head of the left and right linked list.Step3: Call finalMerge() given the arguments new heads of left and right sub-linked lists and store the final head returned after merging.Step4: Return the final head of the sorted linked list.

In the above paragraphs we have discussed how **merge sort **works so in a similar manner here also we first divide the linked list into two sub-list and then recursively sort the two sub-lists and then finally merge both of them and return the final list.

Discussing the algorithm it looks something like this.

## Algorithm:

In the very **first step** as stated you will have to divide the list into two sub-lists as explained with the algorithm below:

start fundtion divideList(headList){

slowPointer = headList

fastPointer = next of headList

start while(slowPointer is not NULL and (fastPointer is not NULL and next of fastPointer is not NULL)){

slowPointer = next of slowPointer

fastPointer = next of next of fastPointer

end while return slowPointerend divideList

The above algorithm to divide a linked list into two halves is popularly known as the **tortoise and hare algorithm**

Now, after dividing the list into two sub-lists we will be sorting each of the two sub-lists based on the actual **merge sorting **algorithm as explained with the algorithm below:

start function finalMerge(firstListHead, secondListHead)

firstHalf = new node

secondHalf = new node

firsthalf = secondHalf /* points to the head node later after sorting */ start while(firstListHead is not NULL && secondListHead is not NULL){

start if(data of firstListHead node <= data of secondListHead node)

next of secondHalf = firstListHead

firstListHead = next of firstListHead

end if

start else next of secondHalf = secondListHead

secondListHead = next of secondListHead

end else

secondHalf = next of secondHalf

end while /* If first list is not over */

start while(firstListHead is not NULL){

next of secondHalf = firstListHead

firstListHead = next of firstListHead

end while

/* If second list is not over */

start while(secondListHead is not NULL){

next of secondHalf - secondListHead

secondListHead = next of secondListHead

end while return next of firstHalfend sortMerge

Now, after sorting the lists we will have to finally get the head reference of the complete sorted list and this function will also help us in getting the reference to the** first half of the list and second half** of the list using the **divideList() **function. the algorithm looks something like this:

start function sortMerge(headList){

start if(next of headList is NULL)

return headList

end if

midNode = new node

secondHead = new node

midNode = divideList(headList)

secondHead = next of midNode

next of midNode = NULL

finalHead = finalMerge(sortMerge(midNode), sortMerge(secondHead))

return finalHeadend sortMerge

Now, eventually, this explains the complete algorithm on how **merge sort **works for a linked list and how the lists get sorted by the **divide and conquer **approach.

Now, since you already know the algorithm behind the problem so, you can now, write your own functional **code **in your desired programming language.

## Dry Run:

Now, consider this algorithm by taking an example of an unsorted linked list and dry run your test case as I have done here:

Now, you could easily relate that how the list is being sorted one by one and this would make you more clear on how this algorithm works!!

# Analyze:

- Time Complexity:
`O(nlogn)`

, where n is the number of nodes in the linked list. - Space Complexity:
`O(logn)`

, where n is the number of nodes in the linked list. Since we are dividing the list into two sub-lists so we have the given final space complexity as`O(logn)`

**Keep learning and keep growing and also keep exploring more!**

**All the very best!**

For more interesting and informative articles and tips follow me on **Medium**** and ****Linkedin**