Sort a Doubly Linked List using Merge Sort

Given a doubly linked list, sort it using merge sort algorithm.


 

Merge sort is an efficient sorting algorithm which uses divide and conquer technique for sorting a sequence of items. It is stable in nature, which means that the original order of equal elements is preserved in the output.

 
In the previous post, we have discussed the merge sort algorithm on a singly linked list. The merge sort algorithm on doubly linked list works in similar way by splitting the list into two halves, sorting each sublist recursively, and finally merge the both sorted lists together to get single sorted list. The algorithm can be implemented as below:

 

Download   Run Code

Output:

1 -> 2 -> 4 -> 6 -> 7 -> 8 -> 9 -> null

 
The time complexity of above solution is O(nlog(n)).

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
Notify of