• 0

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

How will you implement merge sort on LinkedList.


Posted Answers

  • 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;
       }
}
You need to Sign In to post your solution.