# Merge Sort Algorithm for Singly Linked List (in C and Java)

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

Output:

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

## Java

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.

(2 votes, average: 5.00 out of 5)