{"id":557,"date":"2013-08-07T22:52:46","date_gmt":"2013-08-08T05:52:46","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=557"},"modified":"2021-04-04T23:08:34","modified_gmt":"2021-04-05T06:08:34","slug":"sorting-merge-sort","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=557","title":{"rendered":"Sorting &#8211; Merge Sort"},"content":{"rendered":"<p>Time complexity:<\/p>\n<p>Worst-case: \\(O(nlog(n))\\)<\/p>\n<p>Best-case: \\(O(nlog(n))\\)<\/p>\n<p>Average-case: \\(O(nlog(n))\\)<\/p>\n<p>Merge sort divides the array in half, sorts each of those halves, and them merges them back together.<\/p>\n<p>&nbsp;<\/p>\n<p><!--more--><\/p>\n<p><a href=\"http:\/\/cywang.no-ip.org\/wordpress\/wp-content\/uploads\/2013\/08\/MergeSort.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-large wp-image-559\" src=\"http:\/\/cywang.no-ip.org\/wordpress\/wp-content\/uploads\/2013\/08\/MergeSort-724x1024.jpg\" alt=\"MergeSort\" width=\"584\" height=\"825\" srcset=\"http:\/\/cywang.no-ip.org\/wordpress\/wp-content\/uploads\/2013\/08\/MergeSort-724x1024.jpg 724w, http:\/\/cywang.no-ip.org\/wordpress\/wp-content\/uploads\/2013\/08\/MergeSort-212x300.jpg 212w, http:\/\/cywang.no-ip.org\/wordpress\/wp-content\/uploads\/2013\/08\/MergeSort.jpg 1654w\" sizes=\"auto, (max-width: 584px) 100vw, 584px\" \/><\/a><\/p>\n<pre class=\"brush:cpp;\">void MergeSort(int *list, int size)\r\n{\r\n    partitionStep(list,size, 0, size-1);\r\n}\r\n\r\nvoid mergeStep(int *list, int size, int low, int middle, int high)\r\n{\r\n    int i;\r\n    int *tmpList = (int *)malloc(sizeof(int)*size);\r\n    for(i=0;i&lt;size;i++)\r\n        tmpList[i] = list[i];\r\n    int tmpLeft = low;\r\n    int tmpRight = middle + 1;\r\n    int current = low;\r\n    while( (tmpLeft &lt;= middle) &amp;&amp; (tmpRight &lt;= high) )\r\n    {\r\n        if(tmpList[tmpLeft] &lt;= tmpList[tmpRight])\r\n            list[current++] = tmpList[tmpLeft++];\r\n        else\r\n            list[current++] = tmpList[tmpRight++];\r\n    }\r\n    \r\n    int remaining = middle - tmpLeft;\r\n    for (i=0; i&lt;=remaining; i++)\r\n    {\r\n        list[current+i] = tmpList[tmpLeft+i];\r\n    }\r\n\r\n}\r\n\r\nvoid partitionStep(int *list, int size, int low, int high)\r\n{\r\n    if(low &lt; high)\r\n    {\r\n        int i;\r\n        int middle = (low + high)\/2;\r\n\r\n        partitionStep(list, size, low, middle);\r\n        partitionStep(list, size, middle+1, high);\r\n\r\n        mergeStep(list, size, low, middle, high);\r\n    }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Time complexity: Worst-case: Best-case: Average-case: Merge sort divides the array in half, sorts each of those halves, and them merges them back together. &nbsp;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[24,21],"tags":[],"class_list":["post-557","post","type-post","status-publish","format-standard","hentry","category-chapter-11-sorting-and-searching","category-data-structures-and-algorithms"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/557","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=557"}],"version-history":[{"count":5,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/557\/revisions"}],"predecessor-version":[{"id":858,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/557\/revisions\/858"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=557"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=557"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=557"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}