Merge Sort
- Merge Sort is a popular
divide-and-conquersorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves into onesorted result. - It is an example of a
stable sortthat guaranteesO(n log n)performance in allcases— best, worst, and average.
Approach:
- Divide: Split the array into
twohalves. - Conquer: Recursively
sorteach half using merge sort. - Combine:
Merge the two sortedhalves into one sorted array.
Key Concept: Merge Step
- The key step is merging two sorted arrays efficiently into one
sorted array. - This is done using a
two-pointer approach, comparing elements frombotharrays and adding the smaller one into a new result array.
Time & Space Complexity:
Time Complexity: O(n log n) Divide takes log n steps and merging takes linear time.
Space Complexity: O(n) Additional space is needed to store the merged arrays.
Dry Run
Input: nums = [4, 5, 1, 3, 9]
Step 1: sortArray([4, 5, 1, 3, 9]) mid = 2 left = sortArray([4, 5]) right = sortArray([1, 3, 9]) --- Step 2: sortArray([4, 5]) mid = 1 left = sortArray([4]) → [4] (base case) right = sortArray([5]) → [5] (base case) merge([4], [5]) → [4, 5] --- Step 3: sortArray([1, 3, 9]) mid = 1 left = sortArray([1]) → [1] (base case) right = sortArray([3, 9]) Step 4: sortArray([3, 9]) mid = 1 left = sortArray([3]) → [3] (base case) right = sortArray([9]) → [9] (base case) merge([3], [9]) → [3, 9] merge([1], [3, 9]) → [1, 3, 9] --- Step 5: merge([4, 5], [1, 3, 9]) Compare 4 and 1 → take 1 → [1] Compare 4 and 3 → take 3 → [1, 3] Compare 4 and 9 → take 4 → [1, 3, 4] Compare 5 and 9 → take 5 → [1, 3, 4, 5] Remaining → [9] → [1, 3, 4, 5, 9] Final Sorted Array: [1, 3, 4, 5, 9]
Output: [1, 3, 4, 5, 9]
var sortArray = function(nums) {
if (nums.length <= 1) return nums;
let mid = Math.floor(nums.length / 2);
let left = sortArray(nums.slice(0, mid));
let right = sortArray(nums.slice(mid));
return merge(left, right);
};
function merge(left, right) {
let res = [], i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
res.push(left[i++]);
} else {
res.push(right[j++]);
}
}
return [...res, ...left.slice(i), ...right.slice(j)];
}
class Solution(object):
def sortArray(self, nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = self.sortArray(nums[:mid])
right = self.sortArray(nums[mid:])
return self.merge(left, right)
def merge(self, left, right):
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res.extend(left[i:])
res.extend(right[j:])
return res
class Solution {
public int[] sortArray(int[] nums) {
if (nums.length <= 1) return nums;
int mid = nums.length / 2;
int[] left = sortArray(Arrays.copyOfRange(nums, 0, mid));
int[] right = sortArray(Arrays.copyOfRange(nums, mid, nums.length));
return merge(left, right);
}
private int[] merge(int[] left, int[] right) {
int[] res = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length)
res[k++] = (left[i] < right[j]) ? left[i++] : right[j++];
while (i < left.length) res[k++] = left[i++];
while (j < right.length) res[k++] = right[j++];
return res;
}
}
#include <vector>
using namespace std;
class Solution {
public:
vector sortArray(vector& nums) {
if (nums.size() <= 1) return nums;
int mid = nums.size() / 2;
vector left(nums.begin(), nums.begin() + mid);
vector right(nums.begin() + mid, nums.end());
return merge(sortArray(left), sortArray(right));
}
vector merge(const vector& left, const vector& right) {
vector res;
int i = 0, j = 0;
while (i < (int)left.size() && j < (int)right.size()) {
if (left[i] < right[j]) res.push_back(left[i++]);
else res.push_back(right[j++]);
}
while (i < (int)left.size()) res.push_back(left[i++]);
while (j < (int)right.size()) res.push_back(right[j++]);
return res;
}
};
#include <stdlib.h>
void merge(int* arr, int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int* L = (int*)malloc(n1 * sizeof(int));
int* R = (int*)malloc(n2 * sizeof(int));
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0; j = 0; k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
free(L);
free(R);
}
void mergeSort(int* arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* sortArray(int* nums, int numsSize, int* returnSize) {
int* result = (int*)malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; i++) {
result[i] = nums[i];
}
mergeSort(result, 0, numsSize - 1);
*returnSize = numsSize;
return result;
}
public class Solution {
public int[] SortArray(int[] nums) {
if (nums.Length <= 1) return nums;
int mid = nums.Length / 2;
int[] left = SortArray(nums[..mid]);
int[] right = SortArray(nums[mid..]);
return Merge(left, right);
}
private int[] Merge(int[] left, int[] right) {
int[] res = new int[left.Length + right.Length];
int i = 0, j = 0, k = 0;
while (i < left.Length && j < right.Length)
res[k++] = (left[i] < right[j]) ? left[i++] : right[j++];
while (i < left.Length) res[k++] = left[i++];
while (j < right.Length) res[k++] = right[j++];
return res;
}
}
