What is Merge Sort?
Merge Sort is a popular divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves into one sorted result.
It is an example of a stable sort that guarantees O(n log n) performance in all cases — best, worst, and average.
Approach: Divide & Conquer
- Divide: Split the array into two halves.
- Conquer: Recursively sort each half using merge sort.
- Combine: Merge the two sorted halves 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 from both arrays 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 Example: Merge Sort
Input: [5, 2, 4, 1]
Step 1: Divide
[5, 2, 4, 1] →
[5, 2] and [4, 1] →
[5] and [2] | [4] and [1]
Step 2: Merge
Merge [5] and [2] → [2, 5]
Merge [4] and [1] → [1, 4]
Step 3: Final Merge
Merge [2, 5] and [1, 4]:
Compare 2 and 1 → [1]
Compare 2 and 4 → [1, 2]
Compare 5 and 4 → [1, 2, 4]
Remaining elements → [1, 2, 4, 5]
Output: [1, 2, 4, 5]
/**
* @param {number[]} nums
* @return {number[]}
*/
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)];
}
#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;
}
#include <vector>
using namespace std;
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
if (nums.size() <= 1) return nums;
int mid = nums.size() / 2;
vector<int> left(nums.begin(), nums.begin() + mid);
vector<int> right(nums.begin() + mid, nums.end());
return merge(sortArray(left), sortArray(right));
}
vector<int> merge(const vector<int>& left, const vector<int>& right) {
vector<int> 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;
}
};
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;
}
}
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
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;
}
}
