Merge sort on LinkedList mergesort array sorting linkedlist    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (4823)

How will you implement merge sort on LinkedList.

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit The algorithm works as : If the list is empty or only one element in it, then return the list. Divide the linked list into two parts. Sort these two parts recursively. Merge the sorted parts. Time complexity :- $$O(nlogn)$$.Space complexity :- $$O(1)$$ (This is an improvement over merge sort in array which is $$O(n)$$).public node mergeSort (node list1){ /* Check for empty or single list */ if (list1 == null || list1.next == null) return list1; node list2 = split (list1); list1 = mergeSort (list1); list2 = mergeSort (list2); return merge (list1, list2); }public node split (node list1){ node list2 = list1.next; list1.next = list2.next; list2.next = split (list2.next); return list2; }public node merge (node list1, node list2){ /* if list1 or list2 is null, return the other */ if (list1 == null) return list2; if (list2 == null) return list1; /* Merging */ if (list1.data < list2.data){ list1.next = merge (list1.next, list2); return list1; } else{ list2.next = merge (list1, list2.next); return list2; }}