{"id":11853,"date":"2023-01-20T09:03:32","date_gmt":"2023-01-20T09:03:32","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11853"},"modified":"2023-08-21T06:38:02","modified_gmt":"2023-08-21T06:38:02","slug":"merge-k-sorted-arrays","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/","title":{"rendered":"Merge k Sorted Arrays"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg\" alt=\"\" \/><\/p>\n<p>This article will delve into a renowned challenge known as Merge K Sorted Arrays. This particular problem holds significant prominence and is a common query posed during numerous technical interview sessions.<\/p>\n<h2>How to Merge K Sorted Array<\/h2>\n<p>Given K sorted arrays of size N each, Our task is to merge all the given arrays such that the final output array contains all these elements in sorted order. <\/p>\n<p><strong>Examples:<\/strong><br \/>\n<strong>Input:<\/strong><\/p>\n<pre><code>K = 3, N = 4, \narr1:  {1, 3, 5, 7}, \narr2: {2, 4, 6, 8}, \narr3: {0, 9, 10, 11}<\/code><\/pre>\n<p><strong>Output:<\/strong><\/p>\n<pre><code>0 1 2 3 4 5 6 7 8 9 10 11 <\/code><\/pre>\n<p><strong>Explanation: <\/strong>The output array is a sorted array and it contains all the elements of the given input matrix.<\/p>\n<p><strong>Input:<\/strong><\/p>\n<pre><code>k = 4, n = 4, \narr1:  {13, 15, 16, 17}, \narr2: {2, 4, 6, 8}, \narr3: {0, 9, 10, 11} <\/code><\/pre>\n<p><strong>Output:<\/strong><\/p>\n<pre><code>0 2 4 6 8 9 10 11 13 15 16 17<\/code><\/pre>\n<p><strong>Explanation:<\/strong> The output array is a sorted array and it contains all the elements of the given input matrix.<\/p>\n<h3>Approach 1:<\/h3>\n<p>Naive Approach for Merging k sorted arrays:<\/p>\n<p><strong>Algorithm:<\/strong><br \/>\nCreate an output array of size (N<em>K), copy all elements to the output array, then sort the output array.<br \/>\nStep 1: Creates an output array of size N <\/em> K.<br \/>\nStep 2: Traverses the matrix from beginning to end and inserts all elements into the output array.<br \/>\nStep 3: Sort and print the output array.<\/p>\n<p><strong>Code of the above approach:-<\/strong><\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_11928 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_11928 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_11928 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_11928 .wpsm_nav-tabs > li.active > a, #tab_container_11928 .wpsm_nav-tabs > li.active > a:hover, #tab_container_11928 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_11928 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_11928 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_11928 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_11928 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_11928 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_11928 .wpsm_nav-tabs > li > a:hover , #tab_container_11928 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_11928 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_11928 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_11928 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_11928 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_11928 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_11928 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_11928 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11928 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_11928 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11928 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_11928 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_11928\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_11928\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_11928_1\" aria-controls=\"tabs_desc_11928_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_11928\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_11928_1\">\r\n\t\t\t\t\t\t\t\t<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\">#include &lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n#define N 4\r\n \r\n\/\/ Merge arr1[0..N1-1] and arr2[0..N2-1] into\r\n\/\/ arr3[0..N1+N2-1]\r\nvoid mergeArrays(int arr1[], int arr2[], int N1, int N2,\r\n                 int arr3[])\r\n{\r\n    int i = 0, j = 0, k = 0;\r\n \r\n    \/\/ Traverse both array\r\n    while (i &lt; N1 &amp;&amp; j &lt; N2) {\r\n        \/\/ Check if current element of first\r\n        \/\/ array is smaller than current element\r\n        \/\/ of second array. If yes, store first\r\n        \/\/ array element and increment first array\r\n        \/\/ index. Otherwise do same with second array\r\n        if (arr1[i] &lt; arr2[j])\r\n            arr3[k++] = arr1[i++];\r\n        else\r\n            arr3[k++] = arr2[j++];\r\n    }\r\n \r\n    \/\/ Store remaining elements of first array\r\n    while (i &lt; N1)\r\n        arr3[k++] = arr1[i++];\r\n \r\n    \/\/ Store remaining elements of second array\r\n    while (j &lt; N2)\r\n        arr3[k++] = arr2[j++];\r\n}\r\n \r\n\/\/ A utility function to print array elements\r\nvoid printArray(int arr[], int size)\r\n{\r\n    for (int i = 0; i &lt; size; i++)\r\n        cout &lt;&lt; arr[i] &lt;&lt; \" \";\r\n}\r\n \r\n\/\/ This function takes an array of arrays as an argument and\r\n\/\/ All arrays are assumed to be sorted. It merges them\r\n\/\/ together and prints the final sorted output.\r\nvoid mergeKArrays(int arr[][N], int i, int j, int output[])\r\n{\r\n    \/\/ If one array is in range\r\n    if (i == j) {\r\n        for (int p = 0; p &lt; N; p++)\r\n            output[p] = arr[i][p];\r\n        return;\r\n    }\r\n \r\n    \/\/ if only two arrays are left them merge them\r\n    if (j - i == 1) {\r\n        mergeArrays(arr[i], arr[j], N, N, output);\r\n        return;\r\n    }\r\n \r\n    \/\/ Output arrays\r\n    int out1[N * (((i + j) \/ 2) - i + 1)],\r\n        out2[N * (j - ((i + j) \/ 2))];\r\n \r\n    \/\/ Divide the array into halves\r\n    mergeKArrays(arr, i, (i + j) \/ 2, out1);\r\n    mergeKArrays(arr, (i + j) \/ 2 + 1, j, out2);\r\n \r\n    \/\/ Merge the output array\r\n    mergeArrays(out1, out2, N * (((i + j) \/ 2) - i + 1),\r\n                N * (j - ((i + j) \/ 2)), output);\r\n}\r\n \r\n\/\/ Driver's code\r\nint main()\r\n{\r\n    \/\/ Change N at the top to change number of elements\r\n    \/\/ in an array\r\n    int arr[][N] = { { 2, 6, 12, 34 },\r\n                     { 1, 9, 20, 1000 },\r\n                     { 23, 34, 90, 2000 } };\r\n    int K = sizeof(arr) \/ sizeof(arr[0]);\r\n    int output[N * K];\r\n    mergeKArrays(arr, 0, 2, output);\r\n \r\n    \/\/ Function call\r\n    cout &lt;&lt; \"Merged array is \" &lt;&lt; endl;\r\n    printArray(output, N * K);\r\n \r\n    return 0;\r\n}\r\n<\/pre>\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_11928 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_11928 a\"),jQuery(\"#tab-content_11928\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Input<\/strong><\/p>\n<pre><code>arr1: { 2, 6, 12, 34 },\narr2: { 1, 9, 20, 1000 },\narr3: { 23, 34, 90, 2000 }<\/code><\/pre>\n<p><strong>Output<\/strong><\/p>\n<pre><code>Merged array is \n1 2 6 9 12 20 23 34 34 90 1000 2000<\/code><\/pre>\n<p><strong>Time Complexity:<\/strong> O(N <em> K <\/em> log (N<em>K)), Since the final array is of size N<\/em>K.<br \/>\n<strong>Space Complexity:<\/strong> O(N <em> K), The output array is of size N <\/em> K.<\/p>\n<h3>Approach 2: Merge K Sorted Arrays using Merging:<\/h3>\n<p>In this approach, we start by merging the arrays into two groups. After the first merge, we are left with K\/2 arrays. Now, Merge the array back into the group. This leaves us with a K\/4 array. This approach is similar to mergesort. Split K arrays containing the same number of arrays in half until there are two arrays in the group. After this process, merge the arrays from bottom to top.<\/p>\n<p>Follow the given steps to solve the problem:<\/p>\n<p>Step 1: Create a recursive function that takes K arrays and returns the output array.<\/p>\n<p>Step 2: In the recursive function, if the value of K is 1 then return the array else if the value of K is 2 then merge the two arrays in linear time and return the array.<\/p>\n<p>Step 3: If the value of K is greater than 2 then divide the group of k elements into two equal halves and recursively call the function, i.e 0 to K\/2 array in one recursive function and K\/2 to K array in another recursive function.<br \/>\nStep 4: Print the output array.<\/p>\n<p><strong>Code of the above approach:-<\/strong><\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_11929 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_11929 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_11929 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_11929 .wpsm_nav-tabs > li.active > a, #tab_container_11929 .wpsm_nav-tabs > li.active > a:hover, #tab_container_11929 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_11929 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_11929 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_11929 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_11929 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_11929 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_11929 .wpsm_nav-tabs > li > a:hover , #tab_container_11929 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_11929 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_11929 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_11929 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_11929 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_11929 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_11929 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_11929 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11929 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_11929 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11929 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_11929 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_11929\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_11929\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_11929_1\" aria-controls=\"tabs_desc_11929_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_11929\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_11929_1\">\r\n\t\t\t\t\t\t\t\t<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\">\/\/ C++ program to merge K sorted arrays of size n each.\r\n\r\n#include &lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n#define N 4\r\n\r\n\/\/ Merge arr1[0..N1-1] and arr2[0..N2-1] into\r\n\/\/ arr3[0..N1+N2-1]\r\nvoid mergeArrays(int arr1[], int arr2[], int N1, int N2,\r\n                int arr3[])\r\n{\r\n    int i = 0, j = 0, k = 0;\r\n\r\n    \/\/ Traverse both array\r\n    while (i &lt; N1 &amp;&amp; j &lt; N2) {\r\n        \/\/ Check if current element of first\r\n        \/\/ array is smaller than current element\r\n        \/\/ of second array. If yes, store first\r\n        \/\/ array element and increment first array\r\n        \/\/ index. Otherwise do same with second array\r\n        if (arr1[i] &lt; arr2[j])\r\n            arr3[k++] = arr1[i++];\r\n        else\r\n            arr3[k++] = arr2[j++];\r\n    }\r\n\r\n    \/\/ Store remaining elements of first array\r\n    while (i &lt; N1)\r\n        arr3[k++] = arr1[i++];\r\n\r\n    \/\/ Store remaining elements of second array\r\n    while (j &lt; N2)\r\n        arr3[k++] = arr2[j++];\r\n}\r\n\r\n\/\/ A utility function to print array elements\r\nvoid printArray(int arr[], int size)\r\n{\r\n    for (int i = 0; i &lt; size; i++)\r\n        cout &lt;&lt; arr[i] &lt;&lt; \" \";\r\n}\r\n\r\n\/\/ This function takes an array of arrays as an argument and\r\n\/\/ All arrays are assumed to be sorted. It merges them\r\n\/\/ together and prints the final sorted output.\r\nvoid mergeKArrays(int arr[][N], int i, int j, int output[])\r\n{\r\n    \/\/ If one array is in range\r\n    if (i == j) {\r\n        for (int p = 0; p &lt; N; p++)\r\n            output[p] = arr[i][p];\r\n        return;\r\n    }\r\n\r\n    \/\/ if only two arrays are left them merge them\r\n    if (j - i == 1) {\r\n        mergeArrays(arr[i], arr[j], N, N, output);\r\n        return;\r\n    }\r\n\r\n    \/\/ Output arrays\r\n    int out1[N * (((i + j) \/ 2) - i + 1)],\r\n        out2[N * (j - ((i + j) \/ 2))];\r\n\r\n    \/\/ Divide the array into halves\r\n    mergeKArrays(arr, i, (i + j) \/ 2, out1);\r\n    mergeKArrays(arr, (i + j) \/ 2 + 1, j, out2);\r\n\r\n    \/\/ Merge the output array\r\n    mergeArrays(out1, out2, N * (((i + j) \/ 2) - i + 1),\r\n                N * (j - ((i + j) \/ 2)), output);\r\n}\r\n\r\n\/\/ Driver's code\r\nint main()\r\n{\r\n    \/\/ Change N at the top to change number of elements\r\n    \/\/ in an array\r\n    int arr[][N] = { { 2, 6, 12, 34 },\r\n                    { 1, 9, 20, 1000 },\r\n                    { 23, 34, 90, 2000 } };\r\n    int K = sizeof(arr) \/ sizeof(arr[0]);\r\n    int output[N * K];\r\n    mergeKArrays(arr, 0, 2, output);\r\n\r\n    \/\/ Function call\r\n    cout &lt;&lt; \"Merged array is \" &lt;&lt; endl;\r\n    printArray(output, N * K);\r\n\r\n    return 0;\r\n}\r\n<\/pre>\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_11929 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_11929 a\"),jQuery(\"#tab-content_11929\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Input: <\/strong><\/p>\n<pre><code>arr1: { 2, 6, 12, 34 },\narr2: { 1, 9, 20, 1000 },\narr3: { 23, 34, 90, 2000 }<\/code><\/pre>\n<p><strong>Output<\/strong><\/p>\n<pre><code>Merged array is \n1 2 6 9 12 20 23 34 34 90 1000 2000<\/code><\/pre>\n<p><strong>Time Complexity:<\/strong> O(N <em> K <\/em> log K).  There are log K levels as in each level the K arrays are divided in half and at each level, the K arrays are traversed.<\/p>\n<p><strong>Space Complexity:<\/strong> O(N <em> K <\/em> log K). In each level O(N * K).<\/p>\n<h3>Approach 3: Merge K sorted arrays using Min-Heap:<\/h3>\n<p><strong>Brief about Min-Heap<\/strong><\/p>\n<p>Min-heap is a min priority queue. It is a complete binary tree having a root value smaller than both children\u2019s values. <\/p>\n<pre><code>                                                     2\n                                                   \/  \\\n                                                 4    5\n                                               \/ \\  \n                                             11 6  \n\n                                           Min-Heap<\/code><\/pre>\n<p>We will use a min-heap to get the current minimum value.<\/p>\n<p>The idea is to use a minimum heap. The time complexity of this MinHeap-based solution is the same as O(NK log K). The first step should start by creating a MinHeap and inserting the first element of every k array into it. Now the root element of the min-cluster is the smallest of all elements. Then it removes the minheap&#8217;s root element, inserts it into the output array, and inserts the next element from the array of removed elements. To get the result, we need to continue stepping until there are no more elements in MinHeap.<\/p>\n<p>Follow the given steps to solve the problem:<\/p>\n<p>Step 1: Create a min Heap and insert the first element of all the K arrays.<\/p>\n<p>Step 2: Run a loop until the size of MinHeap is greater than zero. Now, Remove the top element of the MinHeap and print the element. Then, insert the next element from the same array in which the removed element belonged. If the array doesn\u2019t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.<\/p>\n<p>Step 3: Return the output array<\/p>\n<p><strong>Code of the above approach:-<\/strong><\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_11930 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_11930 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_11930 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_11930 .wpsm_nav-tabs > li.active > a, #tab_container_11930 .wpsm_nav-tabs > li.active > a:hover, #tab_container_11930 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_11930 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_11930 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_11930 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_11930 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_11930 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_11930 .wpsm_nav-tabs > li > a:hover , #tab_container_11930 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_11930 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_11930 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_11930 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_11930 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_11930 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_11930 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_11930 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11930 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_11930 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_11930 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_11930 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_11930\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_11930\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_11930_1\" aria-controls=\"tabs_desc_11930_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_11930\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_11930_1\">\r\n\t\t\t\t\t\t\t\t<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\">#include &lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n \r\n#define N 4\r\n \r\n\/\/ A min-heap node\r\nstruct MinHeapNode {\r\n    \/\/ The element to be stored\r\n    int element;\r\n \r\n    \/\/ index of the array from which the element is taken\r\n    int i;\r\n \r\n    \/\/ index of the next element to be picked from the array\r\n    int j;\r\n};\r\n \r\n\/\/ Prototype of a utility function to swap two min-heap\r\n\/\/ nodes\r\nvoid swap(MinHeapNode* x, MinHeapNode* y);\r\n \r\n\/\/ A class for Min Heap\r\nclass MinHeap {\r\n \r\n    \/\/ pointer to array of elements in heap\r\n    MinHeapNode* harr;\r\n \r\n    \/\/ size of min heap\r\n    int heap_size;\r\n \r\npublic:\r\n    \/\/ Constructor: creates a min heap of given size\r\n    MinHeap(MinHeapNode a[], int size);\r\n \r\n    \/\/ to heapify a subtree with root at given index\r\n    void MinHeapify(int);\r\n \r\n    \/\/ to get index of left child of node at index i\r\n    int left(int i) { return (2 * i + 1); }\r\n \r\n    \/\/ to get index of right child of node at index i\r\n    int right(int i) { return (2 * i + 2); }\r\n \r\n    \/\/ to get the root\r\n    MinHeapNode getMin() { return harr[0]; }\r\n \r\n    \/\/ to replace root with new node x and heapify() new\r\n    \/\/ root\r\n    void replaceMin(MinHeapNode x)\r\n    {\r\n        harr[0] = x;\r\n        MinHeapify(0);\r\n    }\r\n};\r\n \r\n\/\/ This function takes an array of arrays as an argument and\r\n\/\/ All arrays are assumed to be sorted. It merges them\r\n\/\/ together and prints the final sorted output.\r\nint* mergeKArrays(int arr[][N], int K)\r\n{\r\n \r\n    \/\/ To store output array\r\n    int* output = new int[N * K];\r\n \r\n    \/\/ Create a min heap with k heap nodes.\r\n    \/\/ Every heap node has first element of an array\r\n    MinHeapNode* harr = new MinHeapNode[K];\r\n    for (int i = 0; i &lt; K; i++) {\r\n \r\n        \/\/ Store the first element\r\n        harr[i].element = arr[i][0];\r\n \r\n        \/\/ index of array\r\n        harr[i].i = i;\r\n \r\n        \/\/ Index of next element to be stored from the array\r\n        harr[i].j = 1;\r\n    }\r\n \r\n    \/\/ Create the heap\r\n    MinHeap hp(harr, K);\r\n \r\n    \/\/ Now one by one get the minimum element from min\r\n    \/\/ heap and replace it with next element of its array\r\n    for (int count = 0; count &lt; N * K; count++) {\r\n        \/\/ Get the minimum element and store it in output\r\n        MinHeapNode root = hp.getMin();\r\n        output[count] = root.element;\r\n \r\n        \/\/ Find the next element that will replace current\r\n        \/\/ root of heap. The next element belongs to same\r\n        \/\/ array as the current root.\r\n        if (root.j &lt; N) {\r\n            root.element = arr[root.i][root.j];\r\n            root.j += 1;\r\n        }\r\n        \/\/ If root was the last element of its array\r\n        \/\/ INT_MAX is for infinite\r\n        else\r\n            root.element = INT_MAX;\r\n \r\n        \/\/ Replace root with next element of array\r\n        hp.replaceMin(root);\r\n    }\r\n \r\n    return output;\r\n}\r\n \r\n\/\/ FOLLOWING ARE IMPLEMENTATIONS OF\r\n\/\/ STANDARD MIN HEAP METHODS FROM CORMEN BOOK\r\n\/\/ Constructor: Builds a heap from a given\r\n\/\/ array a[] of given size\r\nMinHeap::MinHeap(MinHeapNode a[], int size)\r\n{\r\n    heap_size = size;\r\n    harr = a; \/\/ store address of array\r\n    int i = (heap_size - 1) \/ 2;\r\n    while (i &gt;= 0) {\r\n        MinHeapify(i);\r\n        i--;\r\n    }\r\n}\r\n \r\n\/\/ A recursive method to heapify a\r\n\/\/ subtree with root at given index.\r\n\/\/ This method assumes that the subtrees\r\n\/\/ are already heapified\r\nvoid MinHeap::MinHeapify(int i)\r\n{\r\n    int l = left(i);\r\n    int r = right(i);\r\n    int smallest = i;\r\n \r\n    if (l &lt; heap_size &amp;&amp; harr[l].element &lt; harr[i].element)\r\n        smallest = l;\r\n \r\n    if (r &lt; heap_size\r\n        &amp;&amp; harr[r].element &lt; harr[smallest].element)\r\n        smallest = r;\r\n \r\n    if (smallest != i) {\r\n        swap(&amp;harr[i], &amp;harr[smallest]);\r\n        MinHeapify(smallest);\r\n    }\r\n}\r\n \r\n\/\/ A utility function to swap two elements\r\nvoid swap(MinHeapNode* x, MinHeapNode* y)\r\n{\r\n    MinHeapNode temp = *x;\r\n    *x = *y;\r\n    *y = temp;\r\n}\r\n \r\n\/\/ A utility function to print array elements\r\nvoid printArray(int arr[], int size)\r\n{\r\n    for (int i = 0; i &lt; size; i++)\r\n        cout &lt;&lt; arr[i] &lt;&lt; \" \";\r\n}\r\n \r\n\/\/ Driver's code\r\nint main()\r\n{\r\n    \/\/ Change N at the top to change number of elements\r\n    \/\/ in an array\r\n    int arr[][N] = { { 2, 6, 12, 34 },\r\n                     { 1, 9, 20, 1000 },\r\n                     { 23, 34, 90, 2000 } };\r\n    int K = sizeof(arr) \/ sizeof(arr[0]);\r\n \r\n    \/\/ Function call\r\n    int* output = mergeKArrays(arr, K);\r\n \r\n    cout &lt;&lt; \"Merged array is \" &lt;&lt; endl;\r\n    printArray(output, N * K);\r\n \r\n    return 0;\r\n}\r\n<\/pre>\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_11930 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_11930 a\"),jQuery(\"#tab-content_11930\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Input:<\/strong><\/p>\n<pre><code>arr1: { 2, 6, 12, 34 },\narr2: { 1, 9, 20, 1000 },\narr3: { 23, 34, 90, 2000 }<\/code><\/pre>\n<p><strong>Output:<\/strong><\/p>\n<pre><code>Merged array is \n1 2 6 9 12 20 23 34 34 90 1000 2000<\/code><\/pre>\n<p><strong>Time Complexity: <\/strong>O(N <em> K <\/em> log K), Insertion and deletion in a Min Heap requires log k time.<br \/>\n<strong>Space Complexity:<\/strong> O(K), If the output is not stored, then the only space required is the Min-Heap of K elements.<\/p>\n<p><strong>Conclusion:<\/strong><br \/>\nIn conclusion, the process of merging K sorted arrays presents an essential problem-solving challenge often encountered in technical interviews. Employing a method reminiscent of mergesort, the arrays are systematically partitioned and merged to achieve an efficient merging of the K sorted arrays into a single, sorted array. This approach not only demonstrates algorithmic prowess but also showcases an ability to optimize array manipulation and merging operations.<\/p>\n<h2>Frequently Asked Questions (FAQs) related to merging K sorted arrays<\/h2>\n<p>Below are some FAQs related to Merge K Sorted Arrays:                                       <\/p>\n<p><strong>1. Why is the problem of merging K sorted arrays significant?<\/strong><br \/>\nMerging K sorted arrays is a fundamental problem in computer science and has practical applications in various domains, including data analysis, database management, and efficient sorting algorithms.<\/p>\n<p><strong>2. What is the time complexity of merging K sorted arrays using the described approach?<\/strong><br \/>\nThe time complexity of this approach is O(N <em> K <\/em> log(K)), where N is the average length of the arrays. The log(K) factor arises from the number of times the arrays are divided into groups.<\/p>\n<p><strong>3. Are there alternative methods for merging K sorted arrays?<\/strong><br \/>\nYes, there are other techniques, such as using priority queues (min-heaps), which can achieve a similar result with potentially better time complexity, around O(N * log(K)).<\/p>\n<p><strong>4. Can the described approach be extended to merging more than K sorted arrays?<\/strong><br \/>\nYes, the approach can be extended to merging more than K sorted arrays by consistently dividing and merging the arrays in groups until the desired result is achieved.<\/p>\n<p><strong>5. What are the main challenges when implementing the merging of K sorted arrays?<\/strong><br \/>\nThe main challenges include managing indices while iterating through the arrays, efficiently selecting the minimum element for merging, and handling edge cases when arrays have different lengths.<\/p>\n<p><strong>6. Is there a trade-off between time complexity and memory usage in merging K sorted arrays?<\/strong><br \/>\nYes, some advanced techniques may optimize for time complexity but require more memory, while others optimize memory usage at the cost of slightly higher time complexity. The choice depends on the specific constraints of the problem.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This article will delve into a renowned challenge known as Merge K Sorted Arrays. This particular problem holds significant prominence and is a common query posed during numerous technical interview sessions. How to Merge K Sorted Array Given K sorted arrays of size N each, Our task is to merge all the given arrays such [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[163],"tags":[],"class_list":["post-11853","post","type-post","status-publish","format-standard","hentry","category-arrays"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Merge k Sorted Arrays<\/title>\n<meta name=\"description\" content=\"Here we will learn about a famous problem called merge k sorted arrays. we will also learn different approaches to merge k sorted array.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Merge k Sorted Arrays\" \/>\n<meta property=\"og:description\" content=\"Here we will learn about a famous problem called merge k sorted arrays. we will also learn different approaches to merge k sorted array.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2023-01-20T09:03:32+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-08-21T06:38:02+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Merge k Sorted Arrays\",\"datePublished\":\"2023-01-20T09:03:32+00:00\",\"dateModified\":\"2023-08-21T06:38:02+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/\"},\"wordCount\":1075,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg\",\"articleSection\":[\"Arrays\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/\",\"name\":\"Merge k Sorted Arrays\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg\",\"datePublished\":\"2023-01-20T09:03:32+00:00\",\"dateModified\":\"2023-08-21T06:38:02+00:00\",\"description\":\"Here we will learn about a famous problem called merge k sorted arrays. we will also learn different approaches to merge k sorted array.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Arrays\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/arrays\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Merge k Sorted Arrays\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Merge k Sorted Arrays","description":"Here we will learn about a famous problem called merge k sorted arrays. we will also learn different approaches to merge k sorted array.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/","og_locale":"en_US","og_type":"article","og_title":"Merge k Sorted Arrays","og_description":"Here we will learn about a famous problem called merge k sorted arrays. we will also learn different approaches to merge k sorted array.","og_url":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2023-01-20T09:03:32+00:00","article_modified_time":"2023-08-21T06:38:02+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Merge k Sorted Arrays","datePublished":"2023-01-20T09:03:32+00:00","dateModified":"2023-08-21T06:38:02+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/"},"wordCount":1075,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg","articleSection":["Arrays"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/","url":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/","name":"Merge k Sorted Arrays","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg","datePublished":"2023-01-20T09:03:32+00:00","dateModified":"2023-08-21T06:38:02+00:00","description":"Here we will learn about a famous problem called merge k sorted arrays. we will also learn different approaches to merge k sorted array.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1674124267987-Merge%20k%20Sorted%20Arrays.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/merge-k-sorted-arrays\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Arrays","item":"https:\/\/prepbytes.com\/blog\/category\/arrays\/"},{"@type":"ListItem","position":3,"name":"Merge k Sorted Arrays"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/11853","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=11853"}],"version-history":[{"count":7,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/11853\/revisions"}],"predecessor-version":[{"id":17680,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/11853\/revisions\/17680"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=11853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=11853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=11853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}