Merge Sort
On this page
Revision notes
Merge Sort (interview style)
Video: “I Had 5 Minutes to Write Merge Sort” on LearnWithKiriti (Kodee and Mr. Tock).
| Folder | Approach | Time | Extra space | Stable |
|---|---|---|---|---|
Optimal-MergeSort/ |
Slice down to single items, merge sorted halves back up | O(n log n) always | O(n) | yes (<= takes ties from the left) |
Brute-InsertionSort/ (bonus, compared in Round 2) |
Pick each card, slide it left into the gap | O(n²) worst, O(n) on sorted input | O(1) | yes |
A million numbers at about a billion steps a second: insertion sort’s worst case needs about 500 billion steps (about 8 minutes); merge sort needs about 20 million (about 0.02 seconds).
Rebuild it from the name
Merge? Slice first! You can only merge two sorted arrays (smaller front goes first). To get sorted arrays, slice the array in half again and again until every piece has one item. One item is already sorted. Merge back up.
Pseudocode
insertionSort(nums):
for pick from 1 to n - 1:
value = nums[pick]
scan = pick - 1
while scan >= 0 and nums[scan] > value:
nums[scan + 1] = nums[scan] # shift, don't swap
scan = scan - 1
nums[scan + 1] = value
mergeSort(nums, low, high):
if low >= high: return # 0 or 1 item: already sorted
mid = low + (high - low) / 2 # never overflows, unlike (low + high) / 2
mergeSort(nums, low, mid)
mergeSort(nums, mid + 1, high)
merge(nums, low, mid, high)
merge(nums, low, mid, high):
temp = new array of size high - low + 1
left = low, right = mid + 1, spot = 0
while left <= mid and right <= high: # both halves still have numbers
if nums[left] <= nums[right]: # <= keeps equal items in order (stable)
temp[spot] = nums[left]; left++
else:
temp[spot] = nums[right]; right++
spot++
copy what is left of the left half, then of the right half (only one has leftovers)
copy temp back into nums starting at low
Why n log n
Halving 8 items: 8 -> 4 -> 2 -> 1, three levels (log₂ 8). Every level merges all n items once. log n levels × n work = O(n log n), in the best, average and worst case.
Without recursion (bottom-up)
Merge pairs of singles, then pairs of 2s, then 4s, and so on, with a loop. Same merge, same O(n log n).
Every program here was compiled, run and random-tested; each prints 1 2 5 8 for [5, 2, 8, 1].
Brute: Insertion Sort
import java.util.Arrays;
public class InsertionSort {
static void insertionSort(int[] nums) {
for (int pick = 1; pick < nums.length; pick++) {
int value = nums[pick];
int scan = pick - 1;
while (scan >= 0 && nums[scan] > value) {
nums[scan + 1] = nums[scan];
scan--;
}
nums[scan + 1] = value;
}
}
public static void main(String[] args) {
int[] nums = {5, 2, 8, 1};
insertionSort(nums);
System.out.println(Arrays.toString(nums)); // [1, 2, 5, 8]
}
}#include <iostream>
#include <vector>
using namespace std;
void insertionSort(vector<int>& nums) {
int size = nums.size();
for (int pick = 1; pick < size; pick++) {
int value = nums[pick];
int scan = pick - 1;
while (scan >= 0 && nums[scan] > value) {
nums[scan + 1] = nums[scan];
scan--;
}
nums[scan + 1] = value;
}
}
int main() {
vector<int> nums = {5, 2, 8, 1};
insertionSort(nums);
for (int x : nums) cout << x << " ";
cout << endl; // 1 2 5 8
return 0;
}def insertion_sort(nums):
for pick in range(1, len(nums)):
value = nums[pick]
scan = pick - 1
while scan >= 0 and nums[scan] > value:
nums[scan + 1] = nums[scan]
scan -= 1
nums[scan + 1] = value
nums = [5, 2, 8, 1]
insertion_sort(nums)
print(nums) # [1, 2, 5, 8]function insertionSort(nums) {
for (let pick = 1; pick < nums.length; pick++) {
let value = nums[pick];
let scan = pick - 1;
while (scan >= 0 && nums[scan] > value) {
nums[scan + 1] = nums[scan];
scan--;
}
nums[scan + 1] = value;
}
}
const nums = [5, 2, 8, 1];
insertionSort(nums);
console.log(nums); // [ 1, 2, 5, 8 ]Optimal: Merge Sort
import java.util.Arrays;
public class MergeSort {
static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int left = low;
int right = mid + 1;
int spot = 0;
while (left <= mid && right <= high) {
if (nums[left] <= nums[right]) {
temp[spot] = nums[left];
left++;
} else {
temp[spot] = nums[right];
right++;
}
spot++;
}
while (left <= mid) {
temp[spot] = nums[left];
left++;
spot++;
}
while (right <= high) {
temp[spot] = nums[right];
right++;
spot++;
}
for (spot = 0; spot < temp.length; spot++) {
nums[low + spot] = temp[spot];
}
}
static void mergeSort(int[] nums, int low, int high) {
if (low >= high) {
return;
}
int mid = low + (high - low) / 2;
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
merge(nums, low, mid, high);
}
public static void main(String[] args) {
int[] nums = {5, 2, 8, 1};
mergeSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums)); // [1, 2, 5, 8]
}
}#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums, int low, int mid, int high) {
vector<int> temp(high - low + 1);
int left = low;
int right = mid + 1;
int spot = 0;
while (left <= mid && right <= high) {
if (nums[left] <= nums[right]) {
temp[spot] = nums[left];
left++;
} else {
temp[spot] = nums[right];
right++;
}
spot++;
}
while (left <= mid) {
temp[spot] = nums[left];
left++;
spot++;
}
while (right <= high) {
temp[spot] = nums[right];
right++;
spot++;
}
for (spot = 0; spot < temp.size(); spot++) {
nums[low + spot] = temp[spot];
}
}
void mergeSort(vector<int>& nums, int low, int high) {
if (low >= high) {
return;
}
int mid = low + (high - low) / 2;
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
merge(nums, low, mid, high);
}
int main() {
vector<int> nums = {5, 2, 8, 1};
mergeSort(nums, 0, nums.size() - 1);
for (int x : nums) cout << x << " ";
cout << endl; // 1 2 5 8
return 0;
}def merge(nums, low, mid, high):
temp = []
left = low
right = mid + 1
while left <= mid and right <= high:
if nums[left] <= nums[right]:
temp.append(nums[left])
left += 1
else:
temp.append(nums[right])
right += 1
while left <= mid:
temp.append(nums[left])
left += 1
while right <= high:
temp.append(nums[right])
right += 1
nums[low:high + 1] = temp
def merge_sort(nums, low, high):
if low >= high:
return
mid = low + (high - low) // 2
merge_sort(nums, low, mid)
merge_sort(nums, mid + 1, high)
merge(nums, low, mid, high)
nums = [5, 2, 8, 1]
merge_sort(nums, 0, len(nums) - 1)
print(nums) # [1, 2, 5, 8]function merge(nums, low, mid, high) {
const temp = new Array(high - low + 1);
let left = low;
let right = mid + 1;
let spot = 0;
while (left <= mid && right <= high) {
if (nums[left] <= nums[right]) {
temp[spot] = nums[left];
left++;
} else {
temp[spot] = nums[right];
right++;
}
spot++;
}
while (left <= mid) {
temp[spot] = nums[left];
left++;
spot++;
}
while (right <= high) {
temp[spot] = nums[right];
right++;
spot++;
}
for (spot = 0; spot < temp.length; spot++) {
nums[low + spot] = temp[spot];
}
}
function mergeSort(nums, low, high) {
if (low >= high) {
return;
}
const mid = low + Math.floor((high - low) / 2);
mergeSort(nums, low, mid);
mergeSort(nums, mid + 1, high);
merge(nums, low, mid, high);
}
const nums = [5, 2, 8, 1];
mergeSort(nums, 0, nums.length - 1);
console.log(nums); // [ 1, 2, 5, 8 ]