Published in

Javarevisited

# Understanding the Algorithm behind Merge Sort for Linked Lists

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).

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

`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.

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.

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

--

--

## Get the Medium app

Hi, I am Swapnil Kant, an avid programmer, and a full-time learner! One who is highly interested in Algorithm Optimization and Development