Problem
Given an array of integers, sort the array in ascending order using the Merge Sort algorithm.Merge Sort follows the divide and conquer approach. It divides the array into two halves until each part contains a single element. It then merges these smaller parts while maintaining sorted order.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [5, 2, 4, 1, 3]Output
[1, 2, 3, 4, 5]Solution
We first divide the array into two halves using the middle index. We recursively divide both halves untill >= r, which means the current portion contains only one element and is already sorted.
After the two halves are sorted, the
merge() method combines them into a single sorted portion. It creates temporary left and right arrays, compares their elements, and places the smaller element back into the original array.
The important part is that both halves are already sorted when
merge() is called, so we only need to compare the current elements from the two halves.
class Solution {
public void mergeSort(int arr[], int l, int r) {
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, r, mid);
}
private void merge(int arr[], int l, int r, int mid) {
int n = mid - l + 1;
int m = r - mid;
int left[] = new int[n];
int right[] = new int[m];
for (int i = 0; i < n; i++) {
left[i] = arr[l + i];
}
for (int j = 0; j < m; j++) {
right[j] = arr[mid + j + 1];
}
int i = 0;
int j = 0;
int k = l;
while (i < n && j < m) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < n) {
arr[k] = left[i];
i++;
k++;
}
while (j < m) {
arr[k] = right[j];
j++;
k++;
}
}
}
Complexity
The array is divided into two halves recursively, resulting inO(log n) levels, and each level processes all n elements during merging.
Therefore, the time complexity is
O(n log n). The temporary left and right arrays require O(n) space, while the recursion stack requires O(log n) space.