Merge Sort Algorithm for Singly Linked List

Given a linked list, sort it using merge sort algorithm.

 
 

Merge sort algorithm is an efficient, general-purpose sorting algorithm which produces a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a comparison sort, i.e. it can sort items of any type for which a less-than relation is defined.

 

Merge sort is a divide and conquer algorithm. Like all divide and conquer algorithms, merge sort algorithm splits the list into two sublists. Then it sort each sublist recursively and finally merge the two sorted lists together to form the answer. Below solution uses FrontBackSplit() and SortedMerge() method to efficiently solve this problem. We have already covered them in detail in previous posts.

C++

Download   Run Code

Output:

1 -> 3 -> 4 -> 6 -> 8 -> 9 -> null

The time complexity of above solution is O(nlogn).
 

Using recursive stack space proportional to the length of a list is not recommended. However, if we change SortedMerge() implementation to iterative one, the recursion in this case is okay as it uses stack space which is proportional to the log of the length of the list. For a 1000 node list, the recursion will only go about 10 deep. For a 2000 node list, it will go 11 deep. If you think about it, you can see that doubling the size of the list only increases the depth by 1.

 
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz