{"id":35680,"date":"2023-12-01T05:12:02","date_gmt":"2023-12-01T05:12:02","guid":{"rendered":"https:\/\/accuweb.cloud\/resource\/faq\/merge-sort-algorithm-java-c-and-python-implementation\/"},"modified":"2026-02-19T11:23:25","modified_gmt":"2026-02-19T11:23:25","slug":"merge-sort-algorithm-java-c-and-python-implementation","status":"publish","type":"faq","link":"https:\/\/accuweb.cloud\/resource\/articles\/merge-sort-algorithm-java-c-and-python-implementation","title":{"rendered":"Merge Sort Algorithm – Java, C, and Python Implementation"},"content":{"rendered":"

Merge Sort Algorithm – Java, C, and Python Implementation<\/h2>\n

Merge sort is a sorting algorithm that divides a list into two halves, sorts each half recursively, and then merges the two sorted halves. This process is repeated until the entire list is sorted.<\/p>\n

The merge sort algorithm is based on the divide and conquer paradigm. This means that the problem of sorting a list is divided into smaller and smaller subproblems until they are trivial to solve. The solutions to the subproblems are then combined to form the solution to the original problem.
\nThe merge sort algorithm is a stable sorting algorithm. It means the order of elements with equal values is preserved in the sorted list.<\/p>\n

The merge sort algorithm is efficient. Its worst-case time complexity is O(n log n), where n is the number of elements in the list.<\/p>\n

Here is an example of how the merge sort algorithm works:<\/p>\n

\"Merge<\/a><\/p>\n

Merge Sort Algorithm in Python<\/h2>\n

Check our developer-friendly Python Hosting!<\/a><\/p>\n

<\/div>\n
def merge_sort(arr):\r\n\tif len(arr) <= 1:\r\n\treturn arr\r\n\t# Split the input array into two halves\r\n\tmid = len(arr) \/\/ 2\r\n\tleft_half = arr[:mid]\r\n\tright_half = arr[mid:]\r\n\t#\u00a0Recursively sort both halves\r\n\tleft_half = merge_sort(left_half)\r\n\tright_half = merge_sort(right_half)\r\n\t# Merge the sorted halves\r\n\treturn merge(left_half, right_half)\r\n\tdef merge(left, right):\r\n\tresult = []\r\n\tleft_idx, right_idx = 0, 0\r\n\twhile left_idx < len(left) and right_idx < len(right):\r\n\tif left[left_idx] < right[right_idx]:\r\n\tresult.append(left[left_idx])\r\n\tleft_idx += 1\r\n\telse:\r\n\tresult.append(right[right_idx])\r\n\tright_idx += 1\r\n\t# Append the remaining elements (if any)\r\n\tresult.extend(left[left_idx:])\r\n\tresult.extend(right[right_idx:])\r\n\treturn result\r\n\t# Example usage with changed variable names\r\n\tif __name__ == \"__main__\":\r\n\tinput_array = [120, 110, 130, 50, 60, 70]\r\n\tprint(\"Original array:\")\r\n\tprint(input_array)\r\n\tsorted_array = merge_sort(input_array)\r\n\tprint(\"Sorted array:\")\r\n\tprint(sorted_array)<\/code><\/pre>\n
Output<\/h3>\n
<\/div>\n
Original array:\r\n\r\n\t120 110 130 50 60 70\r\nSorted array\r\n50 60 70 110 120 130<\/code><\/pre>\n
<\/div>\n\t\t
\n\t\t\t        
\n            \n                        
\n                    
\n        
\n                    \n        \t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t            <\/div>\n        <\/div>\n                    <\/div>\n        <\/section>\n        \t\t<\/div>\n\t\t\n
<\/div>\n
Merge Sort Algorithm in Java Code<\/h2>\n
Check our Containerized Java Hosting Services!<\/a><\/p>\n
<\/div>\n
import java.util.Arrays;\r\npublic class MergeSort {\r\npublic static void mergeSort(int[] array) {\r\n   if (array == null || array.length <= 1) {\r\n   return;\r\n}\r\nint middle = array.length \/ 2;\r\n\/\/ Create two subarrays\r\nint[] leftSubarray = new int[middle];\r\nint[] rightSubarray = new int[array.length - middle];\r\n\/\/ Populate the left and right subarrays\r\nfor (int i = 0; i < middle; i++) {\r\nleftSubarray[i] = array[i];\r\n}\r\n\tfor (int i = middle; i < array.length; i++) {\r\n\trightSubarray[i - middle] = array[i];\r\n}\r\n\/\/ Recursively sort the subarrays\r\nmergeSort(leftSubarray);\r\nmergeSort(rightSubarray);\r\n\/\/ Merge the sorted subarrays\r\nmerge(array, leftSubarray, rightSubarray);\r\n}\r\nprivate static void merge(int[] array, int[] leftSubarray, int[] rightSubarray) {\r\nint i = 0;\u00a0\/\/ Index for the left subarray\r\nint j = 0;\u00a0\/\/ Index for the right subarray\r\nint k = 0;\u00a0\/\/ Index for the merged array\r\nwhile (i < leftSubarray.length && j < rightSubarray.length) {\r\nif (leftSubarray[i] < rightSubarray[j]) {\r\narray[k++] = leftSubarray[i++];\r\n} else {\r\narray[k++] = rightSubarray[j++];\r\n}\r\n}\r\n\/\/ Copy any remaining elements from leftSubarray and rightSubarray\r\nwhile (i < leftSubarray.length) {\r\narray[k++] = leftSubarray[i++];\r\n}\r\nwhile (j < rightSubarray.length) {\r\narray[k++] = rightSubarray[j++];\r\n}\r\n}\r\npublic static void main(String[] args) {\r\nint[] array = {120, 110, 130, 50, 60, 70};\r\nSystem.out.println(\"Original array: \" + Arrays.toString(array));\r\nmergeSort(array);\r\nSystem.out.println(\"Sorted array: \" + Arrays.toString(array));\r\n}\r\n}<\/code><\/pre>\n
<\/div>\n
Output<\/h3>\n
<\/div>\n
Original array: 120 110 130 50 60 70\r\nSorted array 50 60 70 110 120 130<\/code><\/pre>\n
<\/div>\n
Merge Sort Algorithm in C<\/h2>\n
<\/div>\n
#include <stdio.h>\r\nvoid merge(int arr[], int left, int mid, int right) {\r\nint i, j, k;\r\nint n1 = mid - left + 1;\r\nint n2 = right - mid;\r\nint leftSubarray[n1];\r\nint rightSubarray[n2];\r\nfor (i = 0; i < n1; i++)\r\nleftSubarray[i] = arr[left + i];\r\nfor (j = 0; j < n2; j++)\r\nrightSubarray[j] = arr[mid + 1 + j];\r\ni = 0;\r\nj = 0;\r\nk = left;\r\nwhile (i < n1 && j < n2) {\r\nif (leftSubarray[i] <= rightSubarray[j]) {\r\narr[k] = leftSubarray[i];\r\ni++;\r\n} else {\r\narr[k] = rightSubarray[j];\r\nj++;\r\n}\r\nk++;\r\n}\r\nwhile (i < n1) {\r\narr[k] = leftSubarray[i];\r\ni++;\r\nk++;\r\n}\r\nwhile (j < n2) {\r\narr[k] = rightSubarray[j];\r\nj++;\r\nk++;\r\n}\r\n}\r\nvoid mergeSort(int arr[], int left, int right) {\r\nif (left < right) {\r\nint mid = left + (right - left) \/ 2;\r\nmergeSort(arr, left, mid);\r\nmergeSort(arr, mid + 1, right);\r\nmerge(arr, left, mid, right);\r\n}\r\n}\r\nint main() {\r\nint arr[] = {120, 110, 130, 50, 60, 70};\r\nint arr_size = sizeof(arr) \/ sizeof(arr[0]);\r\nprintf(\"Original array: n\");\r\nfor (int i = 0; i < arr_size; i++) {\r\nprintf(\"%d \", arr[i]);\r\n}\r\nprintf(\"n\");\r\nmergeSort(arr, 0, arr_size - 1);\r\nprintf(\"Sorted array: n\");\r\nfor (int i = 0; i < arr_size; i++) {\r\nprintf(\"%d \", arr[i]);\r\n}\r\nprintf(\"n\");\r\nreturn 0;\r\n}\r\n<\/code><\/pre>\n
<\/div>\n
Output<\/h3>\n
<\/div>\n
Original array:\r\n120 110 130 50 60 70\r\nSorted array\r\n50 60 70 110 120 130<\/code><\/pre>\n
<\/div>\n
\t\t
\n\t\t\t        
\n            \n                        
\n                    
\n        
\n                    \n        \t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t
<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t            <\/div>\n        <\/div>\n                    <\/div>\n        <\/section>\n        \t\t<\/div>\n\t\t<\/div>\n
<\/div>\n
Merge Sort Complexity<\/h2>\n
<\/div>\n
-> Time Complexity\r\n* Best - O(n*log n)\r\n* Average - O(n*log n)\r\n* Worst - O(n*log n)\r\n> Space Complexity - O(n)\r\n<\/code><\/pre>\n
<\/div>\n
Explanation<\/h3>\n