Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort.<\/p>\n
For example, the following doubly linked list should be changed to 2<->4<->8<->10<\/p>\n
We strongly recommend to minimize your browser and try this yourself first.<\/strong> Below is the implementation of merge sort for doubly linked list.<\/p>\n Python Programming<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Program%20for%20merge%20sort%20on%20doubly%20linked%20list%0A%20%0A%23%20A%20node%20of%20the%20doublly%20linked%20list%0Aclass%20Node%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%20%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%20%20%20%20%20%20%20self.prev%20%3D%20None%0A%20%0Aclass%20DoublyLinkedList%3A%0A%20%0A%20%20%20%20%20%23%20Constructor%20for%20empty%20Doubly%20Linked%20List%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%20%20%20%23%20Function%20to%20merge%20two%20linked%20list%0A%20%20%20%20def%20merge(self%2C%20first%2C%20second)%3A%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20first%20linked%20list%20is%20empty%0A%20%20%20%20%20%20%20%20if%20first%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20second%20%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20secon%20linked%20list%20is%20empty%20%0A%20%20%20%20%20%20%20%20if%20second%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20first%0A%20%0A%20%20%20%20%20%20%20%20%23%20Pick%20the%20smaller%20value%0A%20%20%20%20%20%20%20%20if%20first.data%20%3C%20second.data%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20first.next%20%3D%20self.merge(first.next%2C%20second)%0A%20%20%20%20%20%20%20%20%20%20%20%20first.next.prev%20%3D%20first%0A%20%20%20%20%20%20%20%20%20%20%20%20first.prev%20%3D%20None%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20first%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20second.next%20%3D%20self.merge(first%2C%20second.next)%0A%20%20%20%20%20%20%20%20%20%20%20%20second.next.prev%20%3D%20second%0A%20%20%20%20%20%20%20%20%20%20%20%20second.prev%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20second%0A%20%0A%20%20%20%20%23%20Function%20to%20do%20merge%20sort%0A%20%20%20%20def%20mergeSort(self%2C%20tempHead)%3A%0A%20%20%20%20%20%20%20%20if%20tempHead%20is%20None%3A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20tempHead%0A%20%20%20%20%20%20%20%20if%20tempHead.next%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20tempHead%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20second%20%3D%20self.split(tempHead)%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Recur%20for%20left%20and%20righ%20halves%0A%20%20%20%20%20%20%20%20tempHead%20%3D%20self.mergeSort(tempHead)%0A%20%20%20%20%20%20%20%20second%20%3D%20self.mergeSort(second)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Merge%20the%20two%20sorted%20halves%0A%20%20%20%20%20%20%20%20return%20self.merge(tempHead%2C%20second)%0A%20%0A%20%20%20%20%23%20Split%20the%20doubly%20linked%20list%20(DLL)%20into%20two%20DLLs%0A%20%20%20%20%23%20of%20half%20sizes%0A%20%20%20%20def%20split(self%2C%20tempHead)%3A%0A%20%20%20%20%20%20%20%20fast%20%3D%20slow%20%3D%20%20tempHead%0A%20%20%20%20%20%20%20%20while(True)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fast.next%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20fast.next.next%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20fast%20%3D%20fast.next.next%0A%20%20%20%20%20%20%20%20%20%20%20%20slow%20%3D%20slow.next%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20temp%20%3D%20slow.next%0A%20%20%20%20%20%20%20%20slow.next%20%3D%20None%0A%20%20%20%20%20%20%20%20return%20temp%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%23%20Given%20a%20reference%20to%20the%20head%20of%20a%20list%20and%20an%0A%20%20%20%20%23%20integer%2Cinserts%20a%20new%20node%20on%20the%20front%20of%20list%0A%20%20%20%20def%20push(self%2C%20new_data)%3A%0A%20%20%0A%20%20%20%20%20%20%20%20%23%201.%20Allocates%20node%0A%20%20%20%20%20%20%20%20%23%202.%20Put%20the%20data%20in%20it%0A%20%20%20%20%20%20%20%20new_node%20%3D%20Node(new_data)%0A%20%20%0A%20%20%20%20%20%20%20%20%23%203.%20Make%20next%20of%20new%20node%20as%20head%20and%0A%20%20%20%20%20%20%20%20%23%20previous%20as%20None%20(already%20None)%0A%20%20%20%20%20%20%20%20new_node.next%20%3D%20self.head%0A%20%20%0A%20%20%20%20%20%20%20%20%23%204.%20change%20prev%20of%20head%20node%20to%20new_node%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.head.prev%20%3D%20new_node%0A%20%20%0A%20%20%20%20%20%20%20%20%23%205.%20move%20the%20head%20to%20point%20to%20the%20new%20node%0A%20%20%20%20%20%20%20%20self.head%20%3D%20new_node%0A%20%0A%20%0A%20%20%20%20def%20printList(self%2C%20node)%3A%0A%20%20%20%20%20%20%20%20temp%20%3D%20node%0A%20%20%20%20%20%20%20%20print%20%22Forward%20Traversal%20using%20next%20poitner%22%0A%20%20%20%20%20%20%20%20while(node%20is%20not%20None)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20node.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20node%20%3D%20node.next%0A%20%20%20%20%20%20%20%20print%20%22%5CnBackward%20Traversal%20using%20prev%20pointer%22%0A%20%20%20%20%20%20%20%20while(temp)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20temp.data%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.prev%0A%20%0A%23%20Driver%20program%20to%20test%20the%20above%20functions%0Adll%20%3D%20DoublyLinkedList()%0Adll.push(5)%0Adll.push(20)%3B%0Adll.push(4)%3B%0Adll.push(3)%3B%0Adll.push(30)%0Adll.push(10)%3B%0Adll.head%20%3D%20dll.mergeSort(dll.head)%20%20%20%0Aprint%20%22Linked%20List%20after%20sorting%22%0Adll.printList(dll.head)\u201d message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n Output:<\/strong><\/p>\n Time Complexity: <\/strong>Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes \u0398(nLogn) time.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":" PYTHON Programming-Merge Sort for Doubly Linked List – Searching and Sorting – Merge sort for singly linked list is already discussed. The important change here is to modify the previous pointers also when merging two lists.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,79476,83481,83517,71670],"tags":[73379,73375,73376,72497,71272,70238,73367,70284,71140,71129,71152,73380,70306,70048,70233,73329,73369,70889,70928,70923,70875,70877,71164,73326,73377,72405,73374,73373,73337,73378,71262,71872,71289,71280,71288,70938,71290,73370,71714,71870,70072,72489,73381,73345,73372,70020,71142,73371,70026,70544],"class_list":["post-25438","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-linked-list","category-merge-sort","category-python-programming","category-searching-and-sorting","tag-algorithm-data-structure","tag-algorithm-for-doubly-linked-list-in-data-structure","tag-algorithm-for-insertion-and-deletion-in-doubly-linked-list","tag-algorithm-for-linked-list","tag-algorithm-for-merge-sort","tag-algorithms-and-data-structures","tag-application-of-linked-list","tag-binary-search-tree-in-data-structure","tag-bubble-sort-in-c-program","tag-bubble-sort-program","tag-c-program-for-bubble-sort","tag-c-programming-interview-questions-pdf","tag-complexity-of-binary-search-algorithm","tag-data-structures","tag-data-structures-and-algorithms","tag-data-structures-and-algorithms-pdf","tag-data-structures-and-algorithms-tutorial","tag-heap-in-data-structure","tag-heap-sort-algorithm","tag-heap-sort-algorithm-in-c","tag-heap-sort-algorithm-with-example","tag-heap-sort-time-complexity","tag-insertion-sort-algorithm-in-data-structure","tag-java-data-structures-and-algorithms","tag-java-solutions","tag-linked-list-algorithm","tag-linked-list-algorithm-in-c","tag-linked-list-in-cpp","tag-linked-list-program-in-c","tag-linkedin","tag-merge-sort-algorithm","tag-merge-sort-algorithm-c-code","tag-merge-sort-algorithm-in-c","tag-merge-sort-c-code","tag-merge-sort-c-program","tag-merge-sort-in-c","tag-merge-sort-in-c-program","tag-merge-two-sorted-linked-list-in-c","tag-quicksort-algorithm-in-data-structure","tag-radix-sort-algorithm-in-data-structure","tag-searching-in-data-structure","tag-singly-linked-list-algorithm","tag-singly-linked-list-in-c-program","tag-singly-linked-list-in-data-structure","tag-singly-linked-list-program-in-c","tag-sorting-algorithms","tag-sorting-in-data-structure","tag-the-worst-case-occur-in-linear-search-algorithm-when","tag-time-complexity-of-binary-search","tag-time-complexity-of-merge-sort"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25438","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25438"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25438\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25438"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25438"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25438"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nMerge sort for singly linked list is already discussed. The important change here is to modify the previous pointers also when merging two lists.<\/p>\nLinked List after sorting\r\nForward Traversal using next pointer\r\n3 4 5 10 20 30\r\nBackward Traversal using prev pointer\r\n30 20 10 5 4 3<\/pre>\n