{"id":25233,"date":"2017-10-15T15:59:52","date_gmt":"2017-10-15T10:29:52","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25233"},"modified":"2017-10-15T15:59:52","modified_gmt":"2017-10-15T10:29:52","slug":"merge-sort-linked-lists-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/merge-sort-linked-lists-2\/","title":{"rendered":"Merge Sort for Linked Lists"},"content":{"rendered":"<p>Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.<span id=\"more-7740\"><\/span><\/p>\n<p>Let head be the first node of the linked list to be sorted and headRef be the pointer to head. Note that we need a reference to head in MergeSort() as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at original head is not the smallest value in linked list.<\/p>\n<pre>MergeSort(headRef)\r\n1) If head is NULL or there is only one element in the Linked List \r\n    then return.\r\n2) Else divide the linked list into two halves.  \r\n      FrontBackSplit(head, &amp;a, &amp;b); \/* a and b are two halves *\/\r\n3) Sort the two halves a and b.\r\n      MergeSort(a);\r\n      MergeSort(b);\r\n4) Merge the sorted a and b (using SortedMerge() discussed <a href=\"http:\/\/www.geeksforgeeks.org\/?p=3622\" target=\"_blank\" rel=\"noopener\">here<\/a>) \r\n   and update the head pointer using headRef.\r\n     *headRef = SortedMerge(a, b);<\/pre>\n<p><strong>C<\/strong><\/p>\n[pastacode lang=&#8221;c&#8221; manual=&#8221;%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20function%20prototypes%20*%2F%0Astruct%20node*%20SortedMerge(struct%20node*%20a%2C%20struct%20node*%20b)%3B%0Avoid%20FrontBackSplit(struct%20node*%20source%2C%0A%20%20%20%20%20%20%20%20%20%20struct%20node**%20frontRef%2C%20struct%20node**%20backRef)%3B%0A%20%0A%2F*%20sorts%20the%20linked%20list%20by%20changing%20next%20pointers%20(not%20data)%20*%2F%0Avoid%20MergeSort(struct%20node**%20headRef)%0A%7B%0A%20%20struct%20node*%20head%20%3D%20*headRef%3B%0A%20%20struct%20node*%20a%3B%0A%20%20struct%20node*%20b%3B%0A%20%0A%20%20%2F*%20Base%20case%20&#8211;%20length%200%20or%201%20*%2F%0A%20%20if%20((head%20%3D%3D%20NULL)%20%7C%7C%20(head-%3Enext%20%3D%3D%20NULL))%0A%20%20%7B%0A%20%20%20%20return%3B%0A%20%20%7D%0A%20%0A%20%20%2F*%20Split%20head%20into%20&#8217;a&#8217;%20and%20&#8217;b&#8217;%20sublists%20*%2F%0A%20%20FrontBackSplit(head%2C%20%26a%2C%20%26b)%3B%20%0A%20%0A%20%20%2F*%20Recursively%20sort%20the%20sublists%20*%2F%0A%20%20MergeSort(%26a)%3B%0A%20%20MergeSort(%26b)%3B%0A%20%0A%20%20%2F*%20answer%20%3D%20merge%20the%20two%20sorted%20lists%20together%20*%2F%0A%20%20*headRef%20%3D%20SortedMerge(a%2C%20b)%3B%0A%7D%0A%20%0A%2F*%20See%20http%3A%2F%2Fwww.geeksforgeeks.org%2F%3Fp%3D3622%20for%20details%20of%20this%20%0A%20%20%20function%20*%2F%0Astruct%20node*%20SortedMerge(struct%20node*%20a%2C%20struct%20node*%20b)%0A%7B%0A%20%20struct%20node*%20result%20%3D%20NULL%3B%0A%20%0A%20%20%2F*%20Base%20cases%20*%2F%0A%20%20if%20(a%20%3D%3D%20NULL)%0A%20%20%20%20%20return(b)%3B%0A%20%20else%20if%20(b%3D%3DNULL)%0A%20%20%20%20%20return(a)%3B%0A%20%0A%20%20%2F*%20Pick%20either%20a%20or%20b%2C%20and%20recur%20*%2F%0A%20%20if%20(a-%3Edata%20%3C%3D%20b-%3Edata)%0A%20%20%7B%0A%20%20%20%20%20result%20%3D%20a%3B%0A%20%20%20%20%20result-%3Enext%20%3D%20SortedMerge(a-%3Enext%2C%20b)%3B%0A%20%20%7D%0A%20%20else%0A%20%20%7B%0A%20%20%20%20%20result%20%3D%20b%3B%0A%20%20%20%20%20result-%3Enext%20%3D%20SortedMerge(a%2C%20b-%3Enext)%3B%0A%20%20%7D%0A%20%20return(result)%3B%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Split%20the%20nodes%20of%20the%20given%20list%20into%20front%20and%20back%20halves%2C%0A%20%20%20%20%20and%20return%20the%20two%20lists%20using%20the%20reference%20parameters.%0A%20%20%20%20%20If%20the%20length%20is%20odd%2C%20the%20extra%20node%20should%20go%20in%20the%20front%20list.%0A%20%20%20%20%20Uses%20the%20fast%2Fslow%20pointer%20strategy.%20%20*%2F%0Avoid%20FrontBackSplit(struct%20node*%20source%2C%0A%20%20%20%20%20%20%20%20%20%20struct%20node**%20frontRef%2C%20struct%20node**%20backRef)%0A%7B%0A%20%20struct%20node*%20fast%3B%0A%20%20struct%20node*%20slow%3B%0A%20%20if%20(source%3D%3DNULL%20%7C%7C%20source-%3Enext%3D%3DNULL)%0A%20%20%7B%0A%20%20%20%20%2F*%20length%20%3C%202%20cases%20*%2F%0A%20%20%20%20*frontRef%20%3D%20source%3B%0A%20%20%20%20*backRef%20%3D%20NULL%3B%0A%20%20%7D%0A%20%20else%0A%20%20%7B%0A%20%20%20%20slow%20%3D%20source%3B%0A%20%20%20%20fast%20%3D%20source-%3Enext%3B%0A%20%0A%20%20%20%20%2F*%20Advance%20&#8217;fast&#8217;%20two%20nodes%2C%20and%20advance%20&#8217;slow&#8217;%20one%20node%20*%2F%0A%20%20%20%20while%20(fast%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20fast%20%3D%20fast-%3Enext%3B%0A%20%20%20%20%20%20if%20(fast%20!%3D%20NULL)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20slow%20%3D%20slow-%3Enext%3B%0A%20%20%20%20%20%20%20%20fast%20%3D%20fast-%3Enext%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20&#8217;slow&#8217;%20is%20before%20the%20midpoint%20in%20the%20list%2C%20so%20split%20it%20in%20two%0A%20%20%20%20%20%20at%20that%20point.%20*%2F%0A%20%20%20%20*frontRef%20%3D%20source%3B%0A%20%20%20%20*backRef%20%3D%20slow-%3Enext%3B%0A%20%20%20%20slow-%3Enext%20%3D%20NULL%3B%0A%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20while(node!%3DNULL)%0A%20%20%7B%0A%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%2F*%20allocate%20node%20*%2F%0A%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%0A%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%0A%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%20%20%20%0A%20%20%0A%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%20%0A%20%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20struct%20node*%20res%20%3D%20NULL%3B%0A%20%20struct%20node*%20a%20%3D%20NULL%3B%0A%20%20%0A%20%20%2F*%20Let%20us%20create%20a%20unsorted%20linked%20lists%20to%20test%20the%20functions%0A%20%20%20Created%20lists%20shall%20be%20a%3A%202-%3E3-%3E20-%3E5-%3E10-%3E15%20*%2F%0A%20%20push(%26a%2C%2015)%3B%0A%20%20push(%26a%2C%2010)%3B%0A%20%20push(%26a%2C%205)%3B%20%0A%20%20push(%26a%2C%2020)%3B%0A%20%20push(%26a%2C%203)%3B%0A%20%20push(%26a%2C%202)%3B%20%0A%20%20%0A%20%20%2F*%20Sort%20the%20above%20created%20Linked%20List%20*%2F%0A%20%20MergeSort(%26a)%3B%0A%20%20%0A%20%20printf(%22%5Cn%20Sorted%20Linked%20List%20is%3A%20%5Cn%22)%3B%0A%20%20printList(a)%3B%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D&#8221; message=&#8221;c&#8221; highlight=&#8221;&#8221; provider=&#8221;manual&#8221;\/]\n<p>Time Complexity: O(nLogn)<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Merge Sort for Linked Lists &#8211; Searching and Sorting &#8211; Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83511,83481,71670],"tags":[71272,71278,72301,72394,70271,72399,72396,71158,72300,72405,72398,72191,72407,70262,71262,71274,71892,71276,72403,71165,71280,72397,72402,71273,71270,71279,72393,72406,71275,71263,71296,71306,72408,71281,72400,71264,72410,72409,71271,71283,70046,72404,71299,72401,72395,71676,70020,71142],"class_list":["post-25233","post","type-post","status-publish","format-standard","hentry","category-linked-lists","category-merge-sort","category-searching-and-sorting","tag-algorithm-for-merge-sort","tag-algorithm-of-merge-sort","tag-array-sort-java","tag-bubble-sort-linked-list-c","tag-heap-sort","tag-java-array-sort","tag-java-merge-sort","tag-java-sort","tag-java-sort-array","tag-linked-list-algorithm","tag-linked-list-sort","tag-list-sort","tag-merge-algorithm","tag-merge-sort","tag-merge-sort-algorithm","tag-merge-sort-algorithm-in-data-structure","tag-merge-sort-algorithm-java","tag-merge-sort-algorithm-with-example","tag-merge-sort-animation","tag-merge-sort-c","tag-merge-sort-c-code","tag-merge-sort-c-code-example","tag-merge-sort-c-example","tag-merge-sort-code","tag-merge-sort-example","tag-merge-sort-example-step-by-step","tag-merge-sort-for-linked-lists","tag-merge-sort-in-c-program-code","tag-merge-sort-in-data-structure","tag-merge-sort-java","tag-merge-sort-java-code","tag-merge-sort-linked-list","tag-merge-sort-linked-list-java","tag-merge-sort-program","tag-merge-sort-program-c","tag-merge-sort-program-in-c","tag-merge-sort-program-in-c-with-output","tag-merge-sort-program-using-c","tag-merge-sort-pseudocode","tag-program-for-merge-sort","tag-quicksort","tag-sort-array-java","tag-sort-linked-list","tag-sort-list","tag-sort-list-java","tag-sorting-a-linked-list","tag-sorting-algorithms","tag-sorting-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25233","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=25233"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25233\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25233"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}