{"id":"8f752cbe-50a6-4674-a384-42a5fb4ac834","name":"Merge Sort","description":"1. You are given an array(arr) of integers.\r\n2. You have to sort the given array in increasing order using the merge sort.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 100000\r\n-10^9 &lt;= arr[i] &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n\r\n#include <vector>\r\n\r\nusing namespace std;\r\n\r\nvoid input(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n}\r\n\r\nvoid print(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cout << arr[i] << \" \";\r\n }\r\n cout << endl;\r\n}\r\n\r\nvector<int> mergeTwoSortedArrays(vector<int> &A, vector<int> &B)\r\n{\r\n if (A.size() == 0 || B.size() == 0)\r\n return A.size() == 0 ? B : A;\r\n\r\n int n = A.size();\r\n int m = B.size();\r\n vector<int> ans(n + m, 0);\r\n\r\n cout << (\"Merging these two arrays \") << endl;\r\n cout << (\"left array -> \");\r\n print(A);\r\n cout << (\"right array -> \");\r\n print(B);\r\n\r\n int i = 0, j = 0, k = 0;\r\n while (i < n && j < m)\r\n {\r\n if (A[i] < B[j])\r\n ans[k++] = A[i++];\r\n else\r\n ans[k++] = B[j++];\r\n }\r\n\r\n while (i < n)\r\n ans[k++] = A[i++];\r\n while (j < m)\r\n ans[k++] = B[j++];\r\n\r\n return ans;\r\n}\r\n\r\nvector<int> mergeSort(vector<int> &arr)\r\n{\r\n \r\n}\r\n\r\nint main()\r\n{\r\n int n, m;\r\n cin >> n;\r\n vector<int> A(n, 0);\r\n input(A);\r\n\r\n vector<int> ans = mergeSort(A);\r\n cout << \"Sorted Array -> \";\r\n print(ans);\r\n return 0;\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int[] mergeSort(int[] arr, int lo, int hi) {\r\n //write your code here\r\n\r\n return null;\r\n }\r\n\r\n //used for merging two sorted arrays\r\n public static int[] mergeTwoSortedArrays(int[] a, int[] b){\r\n System.out.println(\"Merging these two arrays \");\r\n System.out.print(\"left array -> \");\r\n print(a);\r\n System.out.print(\"right array -> \");\r\n print(b);\r\n int i = 0, j =0, k = 0;\r\n int[] ans = new int[a.length + b.length];\r\n while(i < a.length && j < b.length){\r\n if(a[i] <= b[j]){\r\n ans[k] = a[i];\r\n i++;\r\n k++;\r\n }else{\r\n ans[k] = b[j];\r\n j++;\r\n k++;\r\n }\r\n }\r\n\r\n while(i < a.length){\r\n ans[k] = a[i];\r\n k++;\r\n i++;\r\n }\r\n\r\n while(j < b.length){\r\n ans[k] = b[j];\r\n k++;\r\n j++;\r\n }\r\n \r\n return ans;\r\n }\r\n\r\n public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.print(arr[i] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n int[] sa = mergeSort(arr,0,arr.length - 1);\r\n System.out.print(\"Sorted Array -> \");\r\n print(sa);\r\n }\r\n\r\n}"},"python":{"code":"def printList(arr):\n for i in range(len(arr)):\n print(arr[i], end=\" \")\n print()\n\n\ndef merge(arr,l,m,r):\n n1=m-l+1\n n2=r-m\n \n L=[0]*(n1)\n R=[0]*(n2)\n \n print(\"Merging these two arrays \")\n print(\"left array -> \",end=\"\")\n \n for i in range(0,n1):\n L[i]=arr[l+i]\n \n printList(L)\n \n print(\"right array -> \",end=\"\")\n for j in range(0,n2):\n R[j]=arr[m+1+j]\n \n printList(R)\n i=0\n j=0\n k=l\n \n while i<n1 and j<n2:\n if L[i] <=R[j]:\n arr[k]=L[i]\n i+=1\n else:\n arr[k]=R[j]\n j+=1\n k+=1\n \n \n while i<n1:\n arr[k]=L[i]\n i+=1\n k+=1\n \n while j<n2:\n arr[k]=R[j]\n j+=1\n k+=1\n \ndef mergeSort(arr,l,r):\n # write your code\n \n \narr=[]\n\nn=int(input())\n\nfor i in range(0,n):\n ele=int(input())\n \n arr.append(ele)\n \n\nmergeSort(arr,0,n-1)\nprint(\"Sorted Array -> \",end=\"\")\nprintList(arr)"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3","sampleOutput":"Merging these two arrays \r\nleft array -> 7 \r\nright array -> -2 \r\nMerging these two arrays \r\nleft array -> -2 7 \r\nright array -> 4 \r\nMerging these two arrays \r\nleft array -> 1 \r\nright array -> 3 \r\nMerging these two arrays \r\nleft array -> -2 4 7 \r\nright array -> 1 3 \r\nSorted Array -> -2 1 3 4 7","questionVideo":"https://www.youtube.com/embed/aiUHB-3EOg8?end=241","hints":[],"associated":[{"id":"23e744fe-23fe-4816-ad91-74c7e4fa0c68","name":"Which of the following is/are the properties of standard merge sort?","slug":"which-of-the-following-is-are-the-properties-of-standard-merge-sort","type":4},{"id":"b378d293-b55b-4c76-950e-8b6cf5582ef1","name":"What is the worst case time complexity of merge sort?","slug":"what-is-the-worst-case-time-complexity-of-merge-sort","type":4},{"id":"f044e152-d83e-4b86-8790-fcb7316a3640","name":"Which of the following technique is used to implement merge sort?","slug":"which-of-the-following-technique-is-used-to-implement-merge-sort","type":4},{"id":"fc2c4f5a-136c-4003-b9dc-fdff6652a217","name":"Which of the following statement is incorrect about merge sort?","slug":"which-of-the-following-statement-is-incorrect-about-merge-sort","type":4},{"id":"fcef5712-bdf2-42c6-a573-f02c2c853f45","name":"What is the auxiliary space complexity of merge sort?","slug":"what-is-the-auxiliary-space-complexity-of-merge-sort","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8e3abac7-a5ab-4090-abd1-b26ef8b53d70","name":"Time and Space Complexity","slug":"time-and-space-complexity","type":0},{"id":"5fd5ba23-3746-4e63-8afb-b5357edd9e8c","name":"Merge Sort","slug":"merge-sort","type":1}],"next":{"id":"dc5916ba-c7f4-41e2-84c9-3ec1bc0d4b64","name":"Merge Sort","type":3,"slug":"merge-sort"},"prev":{"id":"40fa2cae-069b-4fed-a579-fb2860d12d49","name":"Merge Two Sorted Arrays","type":3,"slug":"merge-two-sorted-arrays"}}}

Merge Sort

1. You are given an array(arr) of integers. 2. You have to sort the given array in increasing order using the merge sort.

{"id":"8f752cbe-50a6-4674-a384-42a5fb4ac834","name":"Merge Sort","description":"1. You are given an array(arr) of integers.\r\n2. You have to sort the given array in increasing order using the merge sort.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 100000\r\n-10^9 &lt;= arr[i] &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\r\n\r\n#include <vector>\r\n\r\nusing namespace std;\r\n\r\nvoid input(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n}\r\n\r\nvoid print(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cout << arr[i] << \" \";\r\n }\r\n cout << endl;\r\n}\r\n\r\nvector<int> mergeTwoSortedArrays(vector<int> &A, vector<int> &B)\r\n{\r\n if (A.size() == 0 || B.size() == 0)\r\n return A.size() == 0 ? B : A;\r\n\r\n int n = A.size();\r\n int m = B.size();\r\n vector<int> ans(n + m, 0);\r\n\r\n cout << (\"Merging these two arrays \") << endl;\r\n cout << (\"left array -> \");\r\n print(A);\r\n cout << (\"right array -> \");\r\n print(B);\r\n\r\n int i = 0, j = 0, k = 0;\r\n while (i < n && j < m)\r\n {\r\n if (A[i] < B[j])\r\n ans[k++] = A[i++];\r\n else\r\n ans[k++] = B[j++];\r\n }\r\n\r\n while (i < n)\r\n ans[k++] = A[i++];\r\n while (j < m)\r\n ans[k++] = B[j++];\r\n\r\n return ans;\r\n}\r\n\r\nvector<int> mergeSort(vector<int> &arr)\r\n{\r\n \r\n}\r\n\r\nint main()\r\n{\r\n int n, m;\r\n cin >> n;\r\n vector<int> A(n, 0);\r\n input(A);\r\n\r\n vector<int> ans = mergeSort(A);\r\n cout << \"Sorted Array -> \";\r\n print(ans);\r\n return 0;\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int[] mergeSort(int[] arr, int lo, int hi) {\r\n //write your code here\r\n\r\n return null;\r\n }\r\n\r\n //used for merging two sorted arrays\r\n public static int[] mergeTwoSortedArrays(int[] a, int[] b){\r\n System.out.println(\"Merging these two arrays \");\r\n System.out.print(\"left array -> \");\r\n print(a);\r\n System.out.print(\"right array -> \");\r\n print(b);\r\n int i = 0, j =0, k = 0;\r\n int[] ans = new int[a.length + b.length];\r\n while(i < a.length && j < b.length){\r\n if(a[i] <= b[j]){\r\n ans[k] = a[i];\r\n i++;\r\n k++;\r\n }else{\r\n ans[k] = b[j];\r\n j++;\r\n k++;\r\n }\r\n }\r\n\r\n while(i < a.length){\r\n ans[k] = a[i];\r\n k++;\r\n i++;\r\n }\r\n\r\n while(j < b.length){\r\n ans[k] = b[j];\r\n k++;\r\n j++;\r\n }\r\n \r\n return ans;\r\n }\r\n\r\n public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.print(arr[i] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n int[] sa = mergeSort(arr,0,arr.length - 1);\r\n System.out.print(\"Sorted Array -> \");\r\n print(sa);\r\n }\r\n\r\n}"},"python":{"code":"def printList(arr):\n for i in range(len(arr)):\n print(arr[i], end=\" \")\n print()\n\n\ndef merge(arr,l,m,r):\n n1=m-l+1\n n2=r-m\n \n L=[0]*(n1)\n R=[0]*(n2)\n \n print(\"Merging these two arrays \")\n print(\"left array -> \",end=\"\")\n \n for i in range(0,n1):\n L[i]=arr[l+i]\n \n printList(L)\n \n print(\"right array -> \",end=\"\")\n for j in range(0,n2):\n R[j]=arr[m+1+j]\n \n printList(R)\n i=0\n j=0\n k=l\n \n while i<n1 and j<n2:\n if L[i] <=R[j]:\n arr[k]=L[i]\n i+=1\n else:\n arr[k]=R[j]\n j+=1\n k+=1\n \n \n while i<n1:\n arr[k]=L[i]\n i+=1\n k+=1\n \n while j<n2:\n arr[k]=R[j]\n j+=1\n k+=1\n \ndef mergeSort(arr,l,r):\n # write your code\n \n \narr=[]\n\nn=int(input())\n\nfor i in range(0,n):\n ele=int(input())\n \n arr.append(ele)\n \n\nmergeSort(arr,0,n-1)\nprint(\"Sorted Array -> \",end=\"\")\nprintList(arr)"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3","sampleOutput":"Merging these two arrays \r\nleft array -> 7 \r\nright array -> -2 \r\nMerging these two arrays \r\nleft array -> -2 7 \r\nright array -> 4 \r\nMerging these two arrays \r\nleft array -> 1 \r\nright array -> 3 \r\nMerging these two arrays \r\nleft array -> -2 4 7 \r\nright array -> 1 3 \r\nSorted Array -> -2 1 3 4 7","questionVideo":"https://www.youtube.com/embed/aiUHB-3EOg8?end=241","hints":[],"associated":[{"id":"23e744fe-23fe-4816-ad91-74c7e4fa0c68","name":"Which of the following is/are the properties of standard merge sort?","slug":"which-of-the-following-is-are-the-properties-of-standard-merge-sort","type":4},{"id":"b378d293-b55b-4c76-950e-8b6cf5582ef1","name":"What is the worst case time complexity of merge sort?","slug":"what-is-the-worst-case-time-complexity-of-merge-sort","type":4},{"id":"f044e152-d83e-4b86-8790-fcb7316a3640","name":"Which of the following technique is used to implement merge sort?","slug":"which-of-the-following-technique-is-used-to-implement-merge-sort","type":4},{"id":"fc2c4f5a-136c-4003-b9dc-fdff6652a217","name":"Which of the following statement is incorrect about merge sort?","slug":"which-of-the-following-statement-is-incorrect-about-merge-sort","type":4},{"id":"fcef5712-bdf2-42c6-a573-f02c2c853f45","name":"What is the auxiliary space complexity of merge sort?","slug":"what-is-the-auxiliary-space-complexity-of-merge-sort","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8e3abac7-a5ab-4090-abd1-b26ef8b53d70","name":"Time and Space Complexity","slug":"time-and-space-complexity","type":0},{"id":"5fd5ba23-3746-4e63-8afb-b5357edd9e8c","name":"Merge Sort","slug":"merge-sort","type":1}],"next":{"id":"dc5916ba-c7f4-41e2-84c9-3ec1bc0d4b64","name":"Merge Sort","type":3,"slug":"merge-sort"},"prev":{"id":"40fa2cae-069b-4fed-a579-fb2860d12d49","name":"Merge Two Sorted Arrays","type":3,"slug":"merge-two-sorted-arrays"}}}
plane

Editor

Loading...

Merge Sort

easy

1. You are given an array(arr) of integers. 2. You have to sort the given array in increasing order using the merge sort.

Constraints

1 <= N <= 100000 -10^9 <= arr[i] <= 10^9

Format

Input

An Integer n arr1 arr2.. n integers

Output

Check the sample output and question video.

Example

Sample Input

5 7 -2 4 1 3

Sample Output

Merging these two arrays left array -> 7 right array -> -2 Merging these two arrays left array -> -2 7 right array -> 4 Merging these two arrays left array -> 1 right array -> 3 Merging these two arrays left array -> -2 4 7 right array -> 1 3 Sorted Array -> -2 1 3 4 7

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode