Merge Sort
Merge sort
Merge sort uses divide and conquer:
- Divide: repeatedly split the sequence into halves.
- Combine: merge the resulting sequences in sorted order.
Merge sort: split and merge through a recursion tree
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Merge two sorted arrays into a third array
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Halving creates levels, with n total merging work per level, giving time. The practical speed of merge sort versus quicksort depends on the input and implementation; neither has a universal speed ranking.
| Time | Extra space | Stability | Design idea |
|---|---|---|---|
| Stable | Divide and conquer |
Merge sort
#include <stdio.h>
#include <string.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef int T;
const int INSERTION_SORT_THRESHOLD = 10;
/**
* Binary Insertion Sort
*/
static T *insertion_sort(T *arr, int n) {
for (int i = 1; i < n; i++) {
T temp = arr[i];
int left = 0;
int right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (temp < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
return arr;
}
/**
* Merge Sort (original v1.0)
*/
T *merge_sort(T *arr, int n) {
if (n <= 1) {
return arr;
}
int mid = n / 2;
T left_half[mid];
T right_half[n - mid];
memcpy(left_half, arr, mid * sizeof(T));
memcpy(right_half, arr + mid, (n - mid) * sizeof(T));
merge_sort(left_half, mid);
merge_sort(right_half, n - mid);
int i = 0;
int j = 0;
int k = 0;
while (i < mid && j < n - mid) {
if (left_half[i] <= right_half[j]) {
arr[k] = left_half[i];
i++;
} else {
arr[k] = right_half[j];
j++;
}
k++;
}
while (i < mid) {
arr[k] = left_half[i];
i++;
k++;
}
while (j < n - mid) {
arr[k] = right_half[j];
j++;
k++;
}
return arr;
}
int main() {
int arr[] = {39, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Take the left item on equality to preserve relative order. The supplied sample's comparison has been corrected from
<to<=.
Merge-sort optimization
Basic merge sort recursively handles tiny subarrays, but frequent method calls can dominate such small problems. Use insertion sort below a small size threshold. This can reduce runtime by 10–15% in some implementations and tests; the actual benefit depends on data, threshold, and environment.
A merge can also be skipped if the sorted ranges and satisfy . The entire range is then already sorted.
Optimized merge sort
#include <stdio.h>
#include <string.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef int T;
const int INSERTION_SORT_THRESHOLD = 10;
/**
* Binary Insertion Sort
*/
static T *insertion_sort(T *arr, int n) {
for (int i = 1; i < n; i++) {
T temp = arr[i];
int left = 0;
int right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (temp < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = temp;
}
return arr;
}
/**
* Merge Sort (original v1.0)
*/
T *merge_sort(T *arr, int n) {
if (n <= INSERTION_SORT_THRESHOLD) {
return insertion_sort(arr, n);
}
int mid = n / 2;
T left_half[mid];
T right_half[n - mid];
memcpy(left_half, arr, mid * sizeof(T));
memcpy(right_half, arr + mid, (n - mid) * sizeof(T));
merge_sort(left_half, mid);
merge_sort(right_half, n - mid);
int i = 0;
int j = 0;
int k = 0;
while (i < mid && j < n - mid) {
if (left_half[i] <= right_half[j]) {
arr[k] = left_half[i];
i++;
} else {
arr[k] = right_half[j];
j++;
}
k++;
}
while (i < mid) {
arr[k] = left_half[i];
i++;
k++;
}
while (j < n - mid) {
arr[k] = right_half[j];
j++;
k++;
}
return arr;
}
int main() {
int arr[] = {39, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Construct a merge tree by hand
Split [8,3,7,2,5] using the sample’s floor(n/2) rule. Draw the recursion tree; show head comparisons, selections, and write-backs at each merge. Single-item ranges need no further split.