Javarevisited
Published in

Javarevisited

Understanding the Algorithm behind Merge Sort for Linked Lists

Merge Sort of 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

Pictorial Representation of Merge Sort

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 finalHead
end 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:

Fig: 1.1
Fig: 1.2
Fig: 1.3
Fig: 1.4
Fig: 1.5

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

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Swapnil Kant

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