{"id":6400,"date":"2025-06-04T20:45:31","date_gmt":"2025-06-04T15:15:31","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=6400"},"modified":"2025-06-04T21:00:17","modified_gmt":"2025-06-04T15:30:17","slug":"merge-sort-code-in-js-c-c-java-python-c","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/merge-sort-code-in-js-c-c-java-python-c\/","title":{"rendered":"Merge Sort &#8211; Code in JS, C, C++, Java, Python, C#"},"content":{"rendered":"\n<!-- Prism.js CSS and JS -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.css\" rel=\"stylesheet\" \/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_code-tabs-container {\n  font-family: \"Segoe UI\", sans-serif !important;\n  max-width: 900px !important;\n  margin: 2rem auto !important;\n  border: 1px solid #ddd !important;\n  border-radius: 8px !important;\n  overflow: hidden !important;\n  background-color: white !important;\n}\n\n.wp_blog_code-tabs-header {\n  background: #f7f7f7 !important;\n  display: flex !important;\n  border-bottom: 1px solid #ddd !important;\n}\n\n.wp_blog_code-tab-button {\n  flex: 1 !important;\n  padding: 10px 15px !important;\n  border: none !important;\n  background: transparent !important;\n  cursor: pointer !important;\n  font-weight: bold !important;\n  transition: background 0.2s !important;\n  color: #242B33 !important;\n}\n\n.wp_blog_code-tab-button.active {\n  background: white !important;\n  border-bottom: 3px solid #0073aa !important;\n}\n\n.wp_blog_code-tab-content {\n  display: none !important;\n  padding: 20px !important;\n  background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content > pre {\n  background: #242B33 !important;\n}\n\n.wp_blog_code-tab-content.active {\n  display: block !important;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0 !important;\n  overflow-x: auto !important;\n}\n\n.wp_blog_explanation {\n  max-width: 900px !important;\n  margin: 2rem auto !important;\n  font-family: \"Segoe UI\", sans-serif !important;\n  line-height: 1.6 !important;\n  background: white !important;\n  color: black !important;\n  padding: 1rem !important;\n  border-radius: 8px !important;\n}\n\n.wp_blog_explanation h2 {\n  color: #0073aa !important;\n  font-size: 1.5rem !important;\n  margin-bottom: 0.5rem !important;\n}\n\n.wp_blog_explanation code {\n  background: #f1f1f1 !important;\n  padding: 2px 6px !important;\n  border-radius: 4px !important;\n  font-family: monospace !important;\n}\n\n.wp_blog_explanation h1,\n.wp_blog_explanation h2,\n.wp_blog_explanation h3,\n.wp_blog_explanation h4,\n.wp_blog_explanation h5,\n.wp_blog_explanation h6,\n.wp_blog_explanation p {\n  margin-top: 10px !important;\n  margin-bottom: 10px !important;\n}\n<\/style>\n\n<!-- \u2705 START: Blog Explanation -->\n<div class=\"wp_blog_explanation\">\n  <h2>What is Merge Sort?<\/h2>\n  <p><strong>Merge Sort<\/strong> is a popular divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves into one sorted result.<\/p>\n  \n  <p>It is an example of a <strong>stable sort<\/strong> that guarantees <strong>O(n log n)<\/strong> performance in all cases \u2014 best, worst, and average.<\/p>\n\n  <h2>Approach: Divide &#038; Conquer<\/h2>\n  <ol>\n    <li><strong>Divide:<\/strong> Split the array into two halves.<\/li>\n    <li><strong>Conquer:<\/strong> Recursively sort each half using merge sort.<\/li>\n    <li><strong>Combine:<\/strong> Merge the two sorted halves into one sorted array.<\/li>\n  <\/ol>\n\n  <h2>Key Concept: Merge Step<\/h2>\n  <p>The key step is merging two sorted arrays efficiently into one sorted array. This is done using a two-pointer approach, comparing elements from both arrays and adding the smaller one into a new result array.<\/p>\n\n  <h2>Time &#038; Space Complexity<\/h2>\n  <ul>\n    <li><strong>Time Complexity:<\/strong> O(n log n) \u2014 Divide takes log n steps and merging takes linear time.<\/li>\n    <li><strong>Space Complexity:<\/strong> O(n) \u2014 Additional space is needed to store the merged arrays.<\/li>\n  <\/ul>\n\n  <h2>Dry Run Example: Merge Sort<\/h2>\n  <p><strong>Input:<\/strong> [5, 2, 4, 1]<\/p>\n  <h3>Step 1: Divide<\/h3>\n  <p>\n    [5, 2, 4, 1] \u2192 <br\/>\n    [5, 2] and [4, 1] \u2192 <br\/>\n    [5] and [2] &nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp; [4] and [1]\n  <\/p>\n  <h3>Step 2: Merge<\/h3>\n  <p>\n    Merge [5] and [2] \u2192 [2, 5] <br\/>\n    Merge [4] and [1] \u2192 [1, 4]\n  <\/p>\n  <h3>Step 3: Final Merge<\/h3>\n  <p>\n    Merge [2, 5] and [1, 4]:<br\/>\n    Compare 2 and 1 \u2192 [1]<br\/>\n    Compare 2 and 4 \u2192 [1, 2]<br\/>\n    Compare 5 and 4 \u2192 [1, 2, 4]<br\/>\n    Remaining elements \u2192 [1, 2, 4, 5]\n  <\/p>\n  <p><strong>Output:<\/strong> [1, 2, 4, 5]<\/p>\n<\/div>\n\n<!-- \u2705 START: Code Tabs -->\n<div class=\"wp_blog_code-tabs-container\">\n  <div class=\"wp_blog_code-tabs-header\">\n    <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n    <button class=\"wp_blog_code-tab-button\" data-lang=\"csharp\">C#<\/button>\n  <\/div>\n\n  <!-- JavaScript -->\n  <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n    <pre><code class=\"language-javascript\">\n\/**\n * @param {number[]} nums\n * @return {number[]}\n *\/\nvar sortArray = function(nums) {\n    if (nums.length <= 1) return nums;\n    let mid = Math.floor(nums.length \/ 2);\n    let left = sortArray(nums.slice(0, mid));\n    let right = sortArray(nums.slice(mid));\n    return merge(left, right);\n};\n\nfunction merge(left, right) {\n    let res = [], i = 0, j = 0;\n    while (i &lt; left.length &#038;&#038; j &lt; right.length) {\n        if (left[i] &lt; right[j]) {\n            res.push(left[i++]);\n        } else {\n            res.push(right[j++]);\n        }\n    }\n    return [...res, ...left.slice(i), ...right.slice(j)];\n}\n    <\/code><\/pre>\n  <\/div>\n\n  <!-- C -->\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n    <pre><code class=\"language-c\">\n  #include &lt;stdlib.h&gt;\n  \n  void merge(int* arr, int l, int m, int r) {\n      int i, j, k;\n      int n1 = m - l + 1;\n      int n2 = r - m;\n  \n      int* L = (int*)malloc(n1 * sizeof(int));\n      int* R = (int*)malloc(n2 * sizeof(int));\n  \n      for (i = 0; i &lt; n1; i++)\n          L[i] = arr[l + i];\n      for (j = 0; j &lt; n2; j++)\n          R[j] = arr[m + 1 + j];\n  \n      i = 0; j = 0; k = l;\n      while (i &lt; n1 &amp;&amp; j &lt; n2) {\n          if (L[i] &lt;= R[j]) {\n              arr[k++] = L[i++];\n          } else {\n              arr[k++] = R[j++];\n          }\n      }\n  \n      while (i &lt; n1) {\n          arr[k++] = L[i++];\n      }\n  \n      while (j &lt; n2) {\n          arr[k++] = R[j++];\n      }\n  \n      free(L);\n      free(R);\n  }\n  \n  void mergeSort(int* arr, int l, int r) {\n      if (l &lt; r) {\n          int m = l + (r - l) \/ 2;\n          mergeSort(arr, l, m);\n          mergeSort(arr, m + 1, r);\n          merge(arr, l, m, r);\n      }\n  }\n  \n  \/**\n   * Note: The returned array must be malloced, assume caller calls free().\n   *\/\n  int* sortArray(int* nums, int numsSize, int* returnSize) {\n      int* result = (int*)malloc(numsSize * sizeof(int));\n      for (int i = 0; i &lt; numsSize; i++) {\n          result[i] = nums[i];\n      }\n      mergeSort(result, 0, numsSize - 1);\n      *returnSize = numsSize;\n      return result;\n  }\n    <\/code><\/pre>\n  <\/div>\n  \n  \n\n  <!-- C++ -->\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n    <pre><code class=\"language-cpp\">\n  #include &lt;vector&gt;\n  using namespace std;\n  \n  class Solution {\n  public:\n      vector&lt;int&gt; sortArray(vector&lt;int&gt;&amp; nums) {\n          if (nums.size() &lt;= 1) return nums;\n          int mid = nums.size() \/ 2;\n          vector&lt;int&gt; left(nums.begin(), nums.begin() + mid);\n          vector&lt;int&gt; right(nums.begin() + mid, nums.end());\n          return merge(sortArray(left), sortArray(right));\n      }\n  \n      vector&lt;int&gt; merge(const vector&lt;int&gt;&amp; left, const vector&lt;int&gt;&amp; right) {\n          vector&lt;int&gt; res;\n          int i = 0, j = 0;\n          while (i &lt; (int)left.size() &amp;&amp; j &lt; (int)right.size()) {\n              if (left[i] &lt; right[j]) res.push_back(left[i++]);\n              else res.push_back(right[j++]);\n          }\n          while (i &lt; (int)left.size()) res.push_back(left[i++]);\n          while (j &lt; (int)right.size()) res.push_back(right[j++]);\n          return res;\n      }\n  };\n    <\/code><\/pre>\n  <\/div>\n  \n\n  <!-- Java -->\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n    <pre><code class=\"language-java\">\nclass Solution {\n    public int[] sortArray(int[] nums) {\n        if (nums.length &lt;= 1) return nums;\n        int mid = nums.length \/ 2;\n        int[] left = sortArray(Arrays.copyOfRange(nums, 0, mid));\n        int[] right = sortArray(Arrays.copyOfRange(nums, mid, nums.length));\n        return merge(left, right);\n    }\n\n    private int[] merge(int[] left, int[] right) {\n        int[] res = new int[left.length + right.length];\n        int i = 0, j = 0, k = 0;\n        while (i &lt; left.length && j &lt; right.length)\n            res[k++] = (left[i] &lt; right[j]) ? left[i++] : right[j++];\n        while (i &lt; left.length) res[k++] = left[i++];\n        while (j &lt; right.length) res[k++] = right[j++];\n        return res;\n    }\n}\n    <\/code><\/pre>\n  <\/div>\n\n  <!-- Python -->\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n    <pre><code class=\"language-python\">\nclass Solution(object):\n    def sortArray(self, nums):\n        if len(nums) &lt;= 1:\n            return nums\n        mid = len(nums) \/\/ 2\n        left = self.sortArray(nums[:mid])\n        right = self.sortArray(nums[mid:])\n        return self.merge(left, right)\n\n    def merge(self, left, right):\n        res = []\n        i = j = 0\n        while i &lt; len(left) and j &lt; len(right):\n            if left[i] &lt; right[j]:\n                res.append(left[i])\n                i += 1\n            else:\n                res.append(right[j])\n                j += 1\n        res.extend(left[i:])\n        res.extend(right[j:])\n        return res\n    <\/code><\/pre>\n  <\/div>\n\n  <!-- C# -->\n  <div class=\"wp_blog_code-tab-content\" data-lang=\"csharp\">\n    <pre><code class=\"language-csharp\">\npublic class Solution {\n    public int[] SortArray(int[] nums) {\n        if (nums.Length &lt;= 1) return nums;\n        int mid = nums.Length \/ 2;\n        int[] left = SortArray(nums[..mid]);\n        int[] right = SortArray(nums[mid..]);\n        return Merge(left, right);\n    }\n\n    private int[] Merge(int[] left, int[] right) {\n        int[] res = new int[left.Length + right.Length];\n        int i = 0, j = 0, k = 0;\n        while (i &lt; left.Length && j &lt; right.Length)\n            res[k++] = (left[i] &lt; right[j]) ? left[i++] : right[j++];\n        while (i &lt; left.Length) res[k++] = left[i++];\n        while (j &lt; right.Length) res[k++] = right[j++];\n        return res;\n    }\n}\n    <\/code><\/pre>\n  <\/div>\n<\/div>\n\n<!-- \u2705 JS Tab Switch Logic -->\n<script>\ndocument.addEventListener('DOMContentLoaded', function () {\n    const buttons = document.querySelectorAll('.wp_blog_code-tab-button');\n    const contents = document.querySelectorAll('.wp_blog_code-tab-content');\n    buttons.forEach(button => {\n        button.addEventListener('click', () => {\n            const lang = button.getAttribute('data-lang');\n            buttons.forEach(btn => btn.classList.remove('active'));\n            button.classList.add('active');\n            contents.forEach(content => {\n                content.classList.toggle('active', content.getAttribute('data-lang') === lang);\n            });\n        });\n    });\n});\n<\/script>\n\n","protected":false},"excerpt":{"rendered":"<p>What is Merge Sort? Merge Sort is a popular divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves into one sorted result. It is an example of a stable sort that guarantees O(n log n) performance in all cases \u2014 best, worst, and average.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[260,175,211,811,810,174,172,173],"tags":[],"class_list":["post-6400","post","type-post","status-publish","format-standard","category-c-c-plus-plus","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-dsa","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6400","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=6400"}],"version-history":[{"count":2,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6400\/revisions"}],"predecessor-version":[{"id":6403,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/6400\/revisions\/6403"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=6400"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=6400"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=6400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}