Merge Sort Algorithm – Java, C, and Python Implementation

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.

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.
The merge sort algorithm is a stable sorting algorithm. It means the order of elements with equal values is preserved in the sorted list.

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.

Here is an example of how the merge sort algorithm works:

Merge Sort Algorithm in Python

Check our developer-friendly Python Hosting!

def merge_sort(arr):
	if len(arr) <= 1:
	return arr
	# Split the input array into two halves
	mid = len(arr) // 2
	left_half = arr[:mid]
	right_half = arr[mid:]
	# Recursively sort both halves
	left_half = merge_sort(left_half)
	right_half = merge_sort(right_half)
	# Merge the sorted halves
	return merge(left_half, right_half)
	def merge(left, right):
	result = []
	left_idx, right_idx = 0, 0
	while left_idx < len(left) and right_idx < len(right):
	if left[left_idx] < right[right_idx]:
	result.append(left[left_idx])
	left_idx += 1
	else:
	result.append(right[right_idx])
	right_idx += 1
	# Append the remaining elements (if any)
	result.extend(left[left_idx:])
	result.extend(right[right_idx:])
	return result
	# Example usage with changed variable names
	if __name__ == "__main__":
	input_array = [120, 110, 130, 50, 60, 70]
	print("Original array:")
	print(input_array)
	sorted_array = merge_sort(input_array)
	print("Sorted array:")
	print(sorted_array)

Output

Original array:

	120 110 130 50 60 70
Sorted array
50 60 70 110 120 130

Merge Sort Algorithm in Java Code

Check our Containerized Java Hosting Services!

import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] array) {
   if (array == null || array.length <= 1) {
   return;
}
int middle = array.length / 2;
// Create two subarrays
int[] leftSubarray = new int[middle];
int[] rightSubarray = new int[array.length - middle];
// Populate the left and right subarrays
for (int i = 0; i < middle; i++) {
leftSubarray[i] = array[i];
}
	for (int i = middle; i < array.length; i++) {
	rightSubarray[i - middle] = array[i];
}
// Recursively sort the subarrays
mergeSort(leftSubarray);
mergeSort(rightSubarray);
// Merge the sorted subarrays
merge(array, leftSubarray, rightSubarray);
}
private static void merge(int[] array, int[] leftSubarray, int[] rightSubarray) {
int i = 0; // Index for the left subarray
int j = 0; // Index for the right subarray
int k = 0; // Index for the merged array
while (i < leftSubarray.length && j < rightSubarray.length) {
if (leftSubarray[i] < rightSubarray[j]) {
array[k++] = leftSubarray[i++];
} else {
array[k++] = rightSubarray[j++];
}
}
// Copy any remaining elements from leftSubarray and rightSubarray
while (i < leftSubarray.length) {
array[k++] = leftSubarray[i++];
}
while (j < rightSubarray.length) {
array[k++] = rightSubarray[j++];
}
}
public static void main(String[] args) {
int[] array = {120, 110, 130, 50, 60, 70};
System.out.println("Original array: " + Arrays.toString(array));
mergeSort(array);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}

Output

Original array: 120 110 130 50 60 70
Sorted array 50 60 70 110 120 130

Merge Sort Algorithm in C

#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int leftSubarray[n1];
int rightSubarray[n2];
for (i = 0; i < n1; i++)
leftSubarray[i] = arr[left + i];
for (j = 0; j < n2; j++)
rightSubarray[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (leftSubarray[i] <= rightSubarray[j]) {
arr[k] = leftSubarray[i];
i++;
} else {
arr[k] = rightSubarray[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftSubarray[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightSubarray[j];
j++;
k++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {120, 110, 130, 50, 60, 70};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: n");
for (int i = 0; i < arr_size; i++) {
printf("%d ", arr[i]);
}
printf("n");
mergeSort(arr, 0, arr_size - 1);
printf("Sorted array: n");
for (int i = 0; i < arr_size; i++) {
printf("%d ", arr[i]);
}
printf("n");
return 0;
}

Output

Original array:
120 110 130 50 60 70
Sorted array
50 60 70 110 120 130

Merge Sort Complexity

-> Time Complexity
* Best - O(n*log n)
* Average - O(n*log n)
* Worst - O(n*log n)
> Space Complexity - O(n)

Explanation

• “Best Case” represents the minimum time an algorithm takes when given the most favorable input.
• “Average Case” represents an algorithm’s expected time when given a typical/random input.
• “Worst Case” represents the maximum time an algorithm takes when given the most unfavorable input.
• “Space complexity” The algorithm’s memory usage is directly proportional to the input size “n.” It means that the algorithm consumes more memory as the input data grows, but this growth is linear, not exponential.

Register and get Auto Scalable instances with a Pay-As-You-Go Pricing Model!

Conclusion

Merge Sort is a highly efficient and stable sorting algorithm known for its consistent O(n*log n) time complexity in all cases (best, average, and worst). It divides the input into smaller segments, sorts them, and then combines them, ensuring reliable and predictable performance for large datasets. However, it requires additional memory for merging, which may be considered in constrained environments