Python Program for Merge Sort in Linked List

Merge Sort is a popular Algorithm used for sorting. It is one of the fastest algorithm to sort a given list or arrays. This algorithm follows a recursive approach to obtain the desired result.

Merge sort says let’s do one thing. Divide the given list or arrays in two part. Let’s name both the parts as ‘a’ and ‘b’. Now we have to sort the both parts(list/arrays) independently, for doing so we will call sort on part ‘a’ and sort on part ‘b’. Once both the parts(list/arrays) are sorted independently, then we will merge these two parts(list/arrays) into one part(list/arrays) which will eventually get sorted.

Sorting both the parts(list/arrays) is the work load of recursion we just have to take care of three things for doing so….. base condition for the recursion, induction hypothesis and the induction step required to do the things done. We will see its implementation further.

Using the similar approach we can merge sort the given linked list too.

Following are the steps required for implementing merge sort in Linked list

1. We will find out the middle of the linked list.
2. Then we will divide the given linked list on the basis of the middle obtained in the step 1
3. Then we will call recursive function on both the halves to get both the halves of linked list sorted.
4. Then we will call the merge function to merge both the sorted linked list in one linked list and return the new head.

finding the middle of the linked list:-

to find out the midpoint of linked list we will have two variable pointing to head, one is slow and the other is fast. Slow will traverse the given linked list at a rate of x(let’s say) and fast will traverse the given linked list at a rate of 2x(let’s say). when the fast will traverse or will be about to traverse the whole linked list, slow will be somewhere at the middle of the list and therefore, we will get the middle as slow.

program for finding middle of the linked list

merging two sorted linked list:-

we will be having heads of the two linked list, we will have to return the new head after merging both the linked list. The head will be the one among both the heads whose value is smaller and after that the comparisons will be done until any of the linked list current pointer does not reaches None.

After being able to do both the required things we are in the position now to write the complete code for the merge sort in the Linked List.

the output for the following input are:-

This is my first article. Hope I was able to give some insights on the topic.