# Mergesort for Singly Linked List

Given a linked list, sort it using mergesort algorithm.

Mergesort 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. Mergesort is a comparison sort, i.e. it can sort items of any type for which a less-than relation is defined.

Mergesort is a divide and conquer algorithm. Like all divide and conquer algorithms, mergeSort split 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++

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.