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

How will you implement merge sort on LinkedList.


Posted Answers

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;
}
}

You need to Sign In to post your solution.