{"id":2569,"date":"2022-04-19T01:06:51","date_gmt":"2022-04-18T17:06:51","guid":{"rendered":"https:\/\/jimmyswebnote.com\/?p=2569"},"modified":"2022-04-19T01:06:52","modified_gmt":"2022-04-18T17:06:52","slug":"merge-sort","status":"publish","type":"post","link":"https:\/\/jimmyswebnote.com\/merge-sort\/","title":{"rendered":"\u6392\u5e8f\u6f14\u7b97\u6cd5\u7b46\u8a18 4 &#8211; Merge Sort (\u5408\u4f75\u6392\u5e8f\u6cd5)"},"content":{"rendered":"\n<p>Merge Sort (\u5408\u4f75\u6392\u5e8f\u6cd5) \u662f\u7b2c\u4e00\u500b\u8981\u4ecb\u7d39\u7684 efficient sort\uff0c\u548c\u524d\u9762\u5e7e\u500b\u6392\u5e8f\u6f14\u7b97\u6cd5\u76f8\u6bd4\u96d6\u7136\u6703\u8907\u96dc\u4e00\u4e9b\uff0c\u4f46\u6642\u9593\u8907\u96dc\u5ea6\u76f8\u8f03\u4e4b\u4e0b\u4e5f\u6703\u6bd4\u8f03\u597d\u3002<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-66335183293c0\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-66335183293c0\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#1_Merge_Sort_%E6%96%B9%E6%B3%95%E4%B8%80\" title=\"1. Merge Sort \u65b9\u6cd5\u4e00\">1. Merge Sort \u65b9\u6cd5\u4e00<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#11_JavaScript_%E5%AF%A6%E4%BD%9C\" title=\"1.1 JavaScript \u5be6\u4f5c\">1.1 JavaScript \u5be6\u4f5c<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#2_Merge_Sort_%E6%96%B9%E6%B3%95%E4%BA%8C\" title=\"2. Merge Sort \u65b9\u6cd5\u4e8c\">2. Merge Sort \u65b9\u6cd5\u4e8c<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#21_JavaScript_%E5%AF%A6%E4%BD%9C\" title=\"2.1 JavaScript \u5be6\u4f5c\">2.1 JavaScript \u5be6\u4f5c<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#3_Merge_Sort_%E6%96%B9%E6%B3%95%E4%B8%89\" title=\"3. Merge Sort \u65b9\u6cd5\u4e09\">3. Merge Sort \u65b9\u6cd5\u4e09<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#31_JavaScript_%E5%AF%A6%E4%BD%9C\" title=\"3.1 JavaScript \u5be6\u4f5c\">3.1 JavaScript \u5be6\u4f5c<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#4_Time_Complexity\" title=\"4. Time Complexity\">4. Time Complexity<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/#4_%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99\" title=\"4. \u53c3\u8003\u8cc7\u6599\">4. \u53c3\u8003\u8cc7\u6599<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"1_Merge_Sort_%E6%96%B9%E6%B3%95%E4%B8%80\"><\/span>1. Merge Sort \u65b9\u6cd5\u4e00<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"11_JavaScript_%E5%AF%A6%E4%BD%9C\"><\/span>1.1 JavaScript \u5be6\u4f5c<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"javascript\" class=\"language-javascript\">function mergeSort1(arr) {\n  if (arr.length &lt; 2) {\n    return arr;\n  } else {\n    \/\/ \u5c07\u9663\u5217\u5207\u534a\n    const middle = Math.floor(arr.length \/ 2);\n    const leftArr = arr.slice(0, middle);\n    const rightArr = arr.slice(middle, arr.length);\n    \/\/ \u5408\u4f75\u6392\u5e8f\u597d\u7684\u5169\u534a\u9663\u5217\n    return merge1(mergeSort1(leftArr), mergeSort1(rightArr));\n  }\n}\n\nfunction merge1(leftArr, rightArr) {\n  const result = [];\n  let leftIndex = 0;\n  let rightIndex = 0;\n\n  while (leftIndex &lt; leftArr.length &amp;&amp; rightIndex &lt; rightArr.length) {\n    if (leftArr[leftIndex] > rightArr[rightIndex]) {\n      result.push(rightArr[rightIndex]);\n      rightIndex++;\n    } else {\n      result.push(leftArr[leftIndex]);\n      leftIndex++;\n    }\n  }\n\n  while (leftIndex &lt; leftArr.length) {\n    result.push(leftArr[leftIndex]);\n    leftIndex++;\n  }\n\n  while (rightIndex &lt; rightArr.length) {\n    result.push(rightArr[rightIndex]);\n    rightIndex++;\n  }\n\n  return result;\n}<\/code><\/pre>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"2_Merge_Sort_%E6%96%B9%E6%B3%95%E4%BA%8C\"><\/span>2. Merge Sort \u65b9\u6cd5\u4e8c<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"21_JavaScript_%E5%AF%A6%E4%BD%9C\"><\/span>2.1 JavaScript \u5be6\u4f5c<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"javascript\" class=\"language-javascript\">function mergeSort2(arr, start = 0, end = arr.length - 1) {\n  if (start === end) {\n    return arr;\n  } else {\n    const middle = Math.floor((start + end) \/ 2);\n    \/\/ \u6392\u5e8f\u5de6\u534a\u90e8\n    mergeSort2(arr, start, middle);\n    \/\/ \u6392\u5e8f\u53f3\u534a\u90e8\n    mergeSort2(arr, middle + 1, end);\n    \/\/ \u5c07\u5169\u534a\u90e8\u6392\u5e8f\u5b8c\u7684\u9663\u5217\u5408\u4f75\n    merge2(arr, start, middle, end);\n    return arr;\n  }\n}\n\nfunction merge2(arr, start, middle, end) {\n  const result = [];\n  let leftIndex = start;\n  let rightIndex = middle + 1;\n\n  while (leftIndex &lt;= middle &amp;&amp; rightIndex &lt;= end) {\n    if (arr[leftIndex] &lt; arr[rightIndex]) {\n      result.push(arr[leftIndex]);\n      leftIndex++;\n    } else {\n      result.push(arr[rightIndex]);\n      rightIndex++;\n    }\n  }\n\n  while (leftIndex &lt;= middle) {\n    result.push(arr[leftIndex]);\n    leftIndex++;\n  }\n\n  while (rightIndex &lt;= end) {\n    result.push(arr[rightIndex]);\n    rightIndex++;\n  }\n\n  for (let i = start; i &lt;= end; i++) {\n    arr[i] = result[i - start];\n  }\n}<\/code><\/pre>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"3_Merge_Sort_%E6%96%B9%E6%B3%95%E4%B8%89\"><\/span>3. Merge Sort \u65b9\u6cd5\u4e09<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3><span class=\"ez-toc-section\" id=\"31_JavaScript_%E5%AF%A6%E4%BD%9C\"><\/span>3.1 JavaScript \u5be6\u4f5c<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"javascript\" class=\"language-javascript\">function mergeSort3(arr) {\n  const n = arr.length;\n  for (let i = 1; i &lt;= n; i *= 2) {\n    for (let j = 0; j + i &lt; n; j += 2 * i) {\n      const start = j;\n      const end = Math.min(j + i * 2 - 1, n - 1);\n      const mid = j + i - 1;\n      merge3(arr, start, mid, end);\n    }\n  }\n  return arr;\n}\n\nfunction merge3(arr, start, middle, end) {\n  const result = [];\n  let leftIndex = start;\n  let rightIndex = middle + 1;\n\n  while (leftIndex &lt;= middle &amp;&amp; rightIndex &lt;= end) {\n    if (arr[leftIndex] &lt; arr[rightIndex]) {\n      result.push(arr[leftIndex]);\n      leftIndex++;\n    } else {\n      result.push(arr[rightIndex]);\n      rightIndex++;\n    }\n  }\n\n  while (leftIndex &lt;= middle) {\n    result.push(arr[leftIndex]);\n    leftIndex++;\n  }\n\n  while (rightIndex &lt;= end) {\n    result.push(arr[rightIndex]);\n    rightIndex++;\n  }\n\n  for (let i = start; i &lt;= end; i++) {\n    arr[i] = result[i - start];\n  }\n}<\/code><\/pre>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"4_Time_Complexity\"><\/span>4. Time Complexity<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>\u6700\u4f73\uff1aO(n log n)<br>\u6700\u5dee\uff1aO(n log n)<br>\u5e73\u5747\uff1aO(n log n)<\/p>\n\n\n\n<h2><span class=\"ez-toc-section\" id=\"4_%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99\"><\/span>4. \u53c3\u8003\u8cc7\u6599<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p><a href=\"https:\/\/www.books.com.tw\/products\/0010883039\" target=\"_blank\" rel=\"noreferrer noopener\">\u5927\u8a71\u8cc7\u6599\u7d50\u69cb(\u5168\u65b0\u5f69\u8272\u7248)<\/a><br><a href=\"https:\/\/www.udemy.com\/course\/algorithm-data-structure\/\" target=\"_blank\" rel=\"noopener\">\u8cc7\u6599\u7d50\u69cb\u8207\u6f14\u7b97\u6cd5 (JavaScript)<\/a><br><a href=\"https:\/\/chupai.github.io\/posts\/200525_sort_algorithm_merge_sort\/\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/chupai.github.io\/posts\/200525_sort_algorithm_merge_sort\/\" rel=\"noreferrer noopener\">JavaScript \u5b78\u6f14\u7b97\u6cd5\uff08\u4e5d\uff09- \u5408\u4f75\u6392\u5e8f<\/a><br><a href=\"https:\/\/blog.techbridge.cc\/2017\/08\/19\/sotring-algorithm\/\" target=\"_blank\" data-type=\"URL\" data-id=\"https:\/\/blog.techbridge.cc\/2017\/08\/19\/sotring-algorithm\/\" rel=\"noreferrer noopener\">\u4e00\u8d77\u7528 JavaScript \u4f86\u8907\u7fd2\u7d93\u5178\u6392\u5e8f\u6cd5\u5427\uff01<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Merge Sort (\u5408\u4f75\u6392\u5e8f\u6cd5) \u662f\u7b2c\u4e00\u500b\u8981\u4ecb\u7d39\u7684 efficient sort\uff0c\u548c\u524d\u9762\u5e7e\u500b\u6392\u5e8f\u6f14\u7b97\u6cd5\u76f8\u6bd4\u96d6\u7136\u6703\u8907\u96dc\u4e00\u4e9b\uff0c\u4f46\u6642\u9593\u8907\u96dc\u5ea6\u76f8\u8f03\u4e4b\u4e0b\u4e5f\u6703\u6bd4\u8f03\u597d\u3002 1. Merge Sort \u65b9\u6cd5\u4e00 &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/jimmyswebnote.com\/merge-sort\/\"> <span class=\"screen-reader-text\">\u6392\u5e8f\u6f14\u7b97\u6cd5\u7b46\u8a18 4 &#8211; Merge Sort (\u5408\u4f75\u6392\u5e8f\u6cd5)<\/span> Read More \u00bb<\/a><\/p>\n","protected":false},"author":1,"featured_media":2573,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[148,147],"tags":[178,179],"_links":{"self":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2569"}],"collection":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/comments?post=2569"}],"version-history":[{"count":4,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2569\/revisions"}],"predecessor-version":[{"id":2575,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/posts\/2569\/revisions\/2575"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/media\/2573"}],"wp:attachment":[{"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/media?parent=2569"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/categories?post=2569"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jimmyswebnote.com\/wp-json\/wp\/v2\/tags?post=2569"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}