15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Merge sort splits an array in half, sorts each half recursively, and merges the two sorted halves into one. A segment of length zero or one is already sorted. It runs in O(n log n) time on every input, needs an O(n) auxiliary array, and is stable when the merge takes the left value on ties.
| Time, all cases | O(n log n): about log n levels, O(n) merge work per level |
|---|---|
| Auxiliary space | O(n) for the aux array, plus O(log n) recursion stack |
| Stable | Yes, when the merge uses A[i] <= A[j] |
| In place | No, the merge writes through an auxiliary array |
| Base case | hi - lo <= 1 returns without splitting |
Assume you can merge two already sorted runs.
For example, merging [1,4] and [2,3] means comparing the front values:
1 and 2; take 1.4 and 2; take 2.4 and 3; take 3.4.The result is [1,2,3,4].
Merge Sort uses that operation in three steps:
A segment of length zero or one needs no sorting. It is already sorted.
For fact checking and further reading:
Use this array throughout the lesson.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 4 | 1 | 3 | 2 |
Input: [4,1,3,2]
Merge Sort first divides the array. It does not compare all four values immediately.
1[4,1,3,2]
2 / \
3[4,1] [3,2]Each length-two segment divides again.
1[4,1] [3,2]
2 / \ / \
3[4] [1] [3] [2]Each singleton run is sorted because it contains only one value. Merging begins from the bottom.
Start with the four-element segment.
Merge Sort on [4, 1, 3, 2]: split in halves down to single values, then merge sorted runs back up: [4]+[1] gives [1, 4], [3]+[2] gives [2, 3], and those merge into [1, 2, 3, 4].
1[4,1,3,2]The midpoint separates the first two positions from the last two positions.
1left segment: indices 0 through 1 -> [4,1]
2right segment: indices 2 through 3 -> [3,2]The halves do not overlap. Together, they cover every input position exactly once.
Split [4,1].
1[4,1] -> [4] and [1]Split [3,2].
1[3,2] -> [3] and [2]The current runs are:
1[4] [1] [3] [2]No recursive call splits further. Each run has length one.
Merge [4] and [1].
| Step | Left head | Right head | Chosen value | Output run |
|---|---|---|---|---|
| Start | 4 | 1 | — | [] |
| Compare | 4 | 1 | 1 | [1] |
| Right run is empty | 4 | — | 4 | [1,4] |
The sorted result for the original left half is [1,4].
Merge [3] and [2].
| Step | Left head | Right head | Chosen value | Output run |
|---|---|---|---|---|
| Start | 3 | 2 | — | [] |
| Compare | 3 | 2 | 2 | [2] |
| Right run is empty | 3 | — | 3 | [2,3] |
The sorted result for the original right half is [2,3].
The array now consists of two sorted neighboring runs:
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 1 | 4 | 2 | 3 |
1[1,4] [2,3]Merge [1,4] with [2,3].
| Step | Left head | Right head | Chosen value | Output run |
|---|---|---|---|---|
| Start | 1 | 2 | — | [] |
| Compare | 1 | 2 | 1 | [1] |
| Compare | 4 | 2 | 2 | [1,2] |
| Compare | 4 | 3 | 3 | [1,2,3] |
| Right run is empty | 4 | — | 4 | [1,2,3,4] |
The final sorted array is:
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 1 | 2 | 3 | 4 |
1[1,2,3,4]After a recursive call finishes, the segment it was given has two properties:
For the example:
[4,1] returns [1,4]. Both values remain, and their order is sorted.[3,2] returns [2,3]. Both values remain.[1,4] and [2,3] returns [1,2,3,4]. It contains every value from both runs.The recursive invariant is:
Every recursive call returns a sorted permutation of the segment it was given; merging two such returned runs yields a sorted permutation of their combined segment.
The word permutation means the output has the same elements with possibly different positions.
A stable merge gives one more guarantee for equal keys. When the current left value and current right value have equal keys, choose the left value first. Then equal records keep their original left-to-right order.
For tagged records:
1[(2,A), (1,X), (2,B)]The two records with key 2 begin in the order A, then B. A left-first tie rule keeps that order after sorting.
Start with a segment from index lo up to, but not including, index hi.
For the example, the full segment is:
1lo = 0
2hi = 4
3A[0..4) = [4,1,3,2]The boundary hi is exclusive. So a segment length is:
1hi - loIf:
1hi - lo <= 1there is nothing to split. Return immediately.
The condition handles both:
1[] length 0
2[8] length 1Use:
1mid = lo + floor((hi - lo) / 2)For [4,1,3,2]:
1lo = 0, hi = 4
2mid = 0 + floor((4 - 0) / 2) = 2The midpoint creates:
1A[0..2) = [4,1]
2A[2..4) = [3,2]The left segment is [lo..mid). The right segment is [mid..hi).
Every position belongs to one half:
lo and less than mid.mid and less than hi.They cannot overlap because no index can be both less than mid and at least mid.
Recursively sort the left segment first. Then recursively sort the right segment.
After those calls return, both halves are sorted.
Use a temporary auxiliary array. Keep one read index at the front of each half:
1i = lo // next unread item in left half
2j = mid // next unread item in right halfWrite the smaller current value into the auxiliary array.
When values compare equal, choose from the left half. That is the stable tie rule.
After one half is exhausted, copy the remaining values from the other half. Then copy the merged result back into the original array segment.
MergeSort sorts the supplied array in place and returns that same array reference. It allocates one auxiliary array whose length matches the input.
SortRange and Merge are helpers. They mutate only the specified segment of A. Their hi boundary is exclusive.
1function MergeSort(A):
2 input: A, an array of comparable values
3 returns: the same array A, sorted in nondecreasing order
4 mutation: rearranges values inside A
5
61. aux = new array of length length(A)
72. SortRange(A, aux, 0, length(A))
83. return A1function SortRange(A, aux, lo, hi):
2 input:
3 A: array to sort
4 aux: auxiliary array with length at least length(A)
5 lo: inclusive start boundary
6 hi: exclusive end boundary
7 contract:
8 On return, A[lo..hi) is a sorted permutation of the values
9 that were in A[lo..hi) when this call began.
10 mutation:
11 May overwrite A[lo..hi) and aux[lo..hi).
12 Does not modify positions outside A[lo..hi).
13
144. if hi - lo <= 1:
155. return
16
176. mid = lo + floor((hi - lo) / 2)
18
197. SortRange(A, aux, lo, mid)
208. SortRange(A, aux, mid, hi)
219. Merge(A, aux, lo, mid, hi)1function Merge(A, aux, lo, mid, hi):
2 input:
3 A[lo..mid) and A[mid..hi) are sorted
4 lo <= mid <= hi
5 contract:
6 On return, A[lo..hi) is a sorted permutation of the two input runs.
7 If equal values are chosen from the left run first, the merge is stable.
8 mutation:
9 Writes aux[lo..hi), then copies those values into A[lo..hi).
10 Does not modify positions outside A[lo..hi).
11
1210. i = lo
1311. j = mid
1412. k = lo
15
1613. while i < mid and j < hi:
1714. if A[i] <= A[j]:
1815. aux[k] = A[i] // left-first rule on equal values
1916. i = i + 1
2017. else:
2118. aux[k] = A[j]
2219. j = j + 1
2320. k = k + 1
24
2521. while i < mid:
2622. aux[k] = A[i]
2723. i = i + 1
2824. k = k + 1
29
3025. while j < hi:
3126. aux[k] = A[j]
3227. j = j + 1
3328. k = k + 1
34
3529. for p = lo to hi - 1:
3630. A[p] = aux[p]Call:
1MergeSort([4,1,3,2])Line 1
1aux = [_,_,_,_]Line 2
1SortRange(A, aux, 0, 4)
2A = [4,1,3,2][0..4)Line 4: 4 - 0 <= 1 is false.
Line 6
1mid = 0 + floor((4 - 0) / 2) = 2Line 7: sort the left segment.
1SortRange(A, aux, 0, 2)[0..2)Line 4: 2 - 0 <= 1 is false.
Line 6
1mid = 0 + floor((2 - 0) / 2) = 1Line 7
1SortRange(A, aux, 0, 1)Line 4: 1 - 0 <= 1 is true. Return.
The segment is [4].
Line 8
1SortRange(A, aux, 1, 2)Line 4: 2 - 1 <= 1 is true. Return.
The segment is [1].
Line 9
1Merge(A, aux, 0, 1, 2)At lines 10–12:
1i = 0
2j = 1
3k = 0At line 13, both runs have unread values.
Line 14: compare A[0] = 4 and A[1] = 1.
4 <= 1 is false.
Lines 18–20
1aux[0] = A[1] = 1
2j = 2
3k = 1
4
5aux = [1,_,_,_]Line 13: j < hi is now 2 < 2, which is false.
Line 21: i < mid is 0 < 1, so copy the left remainder.
Lines 22–24
1aux[1] = A[0] = 4
2i = 1
3k = 2
4
5aux = [1,4,_,_]Line 25: j < hi is false.
Lines 29–30: copy aux[0..2) back into A.
1A = [1,4,3,2]The call SortRange(A, aux, 0, 2) returns.
[2..4)Return to the full call.
Line 8
1SortRange(A, aux, 2, 4)Line 4: 4 - 2 <= 1 is false.
Line 6
1mid = 2 + floor((4 - 2) / 2) = 3Line 7
1SortRange(A, aux, 2, 3)Line 4: 3 - 2 <= 1 is true. Return.
The segment is [3].
Line 8
1SortRange(A, aux, 3, 4)Line 4: 4 - 3 <= 1 is true. Return.
The segment is [2].
Line 9
1Merge(A, aux, 2, 3, 4)At lines 10–12:
1i = 2
2j = 3
3k = 2Line 14: compare A[2] = 3 and A[3] = 2.
3 <= 2 is false.
Lines 18–20
1aux[2] = A[3] = 2
2j = 4
3k = 3
4
5aux = [1,4,2,_]Line 21: i < mid is 2 < 3.
Lines 22–24
1aux[3] = A[2] = 3
2i = 3
3k = 4
4
5aux = [1,4,2,3]Lines 29–30: copy aux[2..4) back.
1A = [1,4,2,3]The call SortRange(A, aux, 2, 4) returns.
Return to the original call.
Line 9
1Merge(A, aux, 0, 2, 4)At lines 10–12:
1i = 0
2j = 2
3k = 0
4
5A = [1,4,2,3]First pass through line 13
Compare A[0] = 1 and A[2] = 2.
Lines 14–16
1aux[0] = 1
2i = 1Line 20
1k = 1
2aux = [1,4,2,3]Only aux[0] is meaningful so far.
Second pass through line 13
Compare A[1] = 4 and A[2] = 2.
Lines 18–20
1aux[1] = 2
2j = 3
3k = 2
4
5aux = [1,2,2,3]Third pass through line 13
Compare A[1] = 4 and A[3] = 3.
Lines 18–20
1aux[2] = 3
2j = 4
3k = 3
4
5aux = [1,2,3,3]Line 13: the right run is exhausted because j = 4.
Line 21: the left run still has A[1] = 4.
Lines 22–24
1aux[3] = 4
2i = 2
3k = 4
4
5aux = [1,2,3,4]Lines 29–30: copy all four values back.
1A = [1,2,3,4]Line 3: MergeSort returns:
1[1,2,3,4]We must show that every call to SortRange(A, aux, lo, hi) returns a sorted permutation of its original segment.
Use a structural argument over the recursive calls.
If hi - lo <= 1, the segment has zero or one value.
So the segment is already a sorted permutation of itself. Lines 4–5 are correct.
Consider a call on a segment with length greater than one.
Line 6 chooses mid between lo and hi. The two halves are:
1A[lo..mid)
2A[mid..hi)These halves cover every input position exactly once:
lo up to mid - 1.mid up to hi - 1.mid separates them, so they do not overlap.By the recursive assumption:
A[lo..mid) is a sorted permutation of its original values.A[mid..hi) is a sorted permutation of its original values.Now consider Merge.
During line 13, the already-written portion aux[lo..k) is sorted and contains exactly the smallest values removed from the two input runs so far.
k = lo, so no values have been written. The statement is true.i or j removes exactly one value from one run, so no value is duplicated or lost.When one run is exhausted, all remaining values in the other run are already sorted. Lines 21–28 append them in order.
Finally, lines 29–30 copy the merged sorted permutation into A[lo..hi).
Therefore, line 9 produces a sorted permutation of the whole segment.
Each non-base call splits a segment into two smaller segments. Their lengths are less than the original length.
Eventually, recursive calls reach segments of length zero or one, where lines 4–5 return. Therefore the recursion terminates.
Since the base case is correct and each recursive step is correct, MergeSort returns a sorted permutation of the input array.
If line 14 uses <=, equal values from the left run are selected before equal values from the right run. Therefore the standard merge is stable.
Consider an input with n elements.
At the bottom of the recursion tree, there are singleton segments. Moving upward, neighboring segments merge.
For a level of the tree, the segments are disjoint. Every element belongs to exactly one merge at that level.
For n = 8, the merge work can be grouped like this:
1Level near the top: 8
2Next level: 4 + 4
3Next level: 2 + 2 + 2 + 2Each level processes a total of n elements.
Each split approximately halves a segment. Halving continues until segments have length one.
The number of levels is O(log n).
At each level, merging does O(n) total work:
aux.A.So the total work is:
1O(n) work per level × O(log n) levels = O(n log n)Merge Sort performs the same splits and merges for the same segment sizes regardless of the original arrangement.
The pseudocode allocates:
1aux = new array of length nSo the auxiliary array uses O(n) space.
The recursion depth is O(log n). The call stack therefore uses O(log n) additional space.
Together:
1O(n) auxiliary array + O(log n) recursion stack = O(n) auxiliary spaceThe input array itself is not counted as auxiliary space.
Incorrect assumption: Every call should split again.
1// Incorrect: no check for hi - lo <= 1
2mid = lo + floor((hi - lo) / 2)
3SortRange(A, aux, lo, mid)
4SortRange(A, aux, mid, hi)Input that exposes it:
1[]The first call is:
1SortRange(A, aux, 0, 0)Its midpoint is still 0, so it calls itself again with the same boundaries:
1SortRange(A, aux, 0, 0)The recursion does not reach a smaller segment.
Correction:
1if hi - lo <= 1:
2 returnIncorrect assumption: The merge helper can merge arbitrary halves.
1Merge(A, aux, lo, mid, hi) // called before recursive sortingInput that exposes it:
1[3,1,2,0]The halves are:
1[3,1] and [2,0]Neither half is sorted. A merge compares only the current heads. It cannot safely conclude that 3 is ready before seeing the later 1, or that 2 is ready before seeing the later 0.
Correction: Sort both halves first.
1SortRange(A, aux, lo, mid)
2SortRange(A, aux, mid, hi)
3Merge(A, aux, lo, mid, hi)Incorrect line:
1copy A[lo..mid) followed by A[mid..hi) into A[lo..hi)Input that exposes it:
1left = [1,4]
2right = [2,3]Concatenation produces:
1[1,4,2,3]The value 4 appears before 2, so the result is not sorted.
Correction: Compare the two run heads until one run is exhausted.
1if A[i] <= A[j]:
2 take A[i]
3else:
4 take A[j]Incorrect line:
1if A[i] < A[j]:
2 take A[i]
3else:
4 take A[j] // takes right on equal keysInput that exposes it:
1[(2,A), (1,X), (2,B)]After sorting the halves, the merge can receive:
1left = [(1,X), (2,A)]
2right = [(2,B)]After taking (1,X), the heads are (2,A) and (2,B).
A right-first tie rule chooses (2,B) before (2,A):
1[(1,X), (2,B), (2,A)]The equal-key records A and B have reversed relative order.
Correction: Choose the left item on equal keys.
1if A[i] <= A[j]:
2 take A[i]
3else:
4 take A[j]| Input | Required result |
|---|---|
[] | [] |
[8] | [8] without another split |
[2,1] | [1,2] after merging singleton runs |
[1,1,1] | Equal tagged records retain order when merge is stable |
[3,1,2] | [1,2,3] despite uneven halves |
Implement stable Merge Sort for an integer array.
Your implementation contract:
Executable tests verify:
1
2def merge_sort(a):
3 aux = [0] * len(a)
4 sort_range(a, aux, 0, len(a))
5 return a
6
7def sort_range(a, aux, lo, hi): # sorts a[lo:hi], hi is exclusive
8 if hi - lo <= 1:
9 return
10 mid = lo + (hi - lo) // 2
11 sort_range(a, aux, lo, mid)
12 sort_range(a, aux, mid, hi)
13 merge(a, aux, lo, mid, hi)
14
15def merge(a, aux, lo, mid, hi):
16 i, j, k = lo, mid, lo
17 while i < mid and j < hi:
18 if a[i] <= a[j]: # left wins ties, so the sort is stable
19 aux[k] = a[i]
20 i += 1
21 else:
22 aux[k] = a[j]
23 j += 1
24 k += 1
25 while i < mid:
26 aux[k] = a[i]
27 i += 1
28 k += 1
29 while j < hi:
30 aux[k] = a[j]
31 j += 1
32 k += 1
33 for p in range(lo, hi): # copy the merged run back
34 a[p] = aux[p]
35
36print(merge_sort([4, 1, 3, 2]))1
2import java.util.Arrays;
3
4public class Main {
5 static int[] mergeSort(int[] a) {
6 int[] aux = new int[a.length];
7 sortRange(a, aux, 0, a.length);
8 return a;
9 }
10
11 static void sortRange(int[] a, int[] aux, int lo, int hi) { // sorts a[lo..hi), hi is exclusive
12 if (hi - lo <= 1) return;
13 int mid = lo + (hi - lo) / 2;
14 sortRange(a, aux, lo, mid);
15 sortRange(a, aux, mid, hi);
16 merge(a, aux, lo, mid, hi);
17 }
18
19 static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
20 int i = lo, j = mid, k = lo;
21 while (i < mid && j < hi) {
22 if (a[i] <= a[j]) aux[k++] = a[i++]; // left wins ties, so the sort is stable
23 else aux[k++] = a[j++];
24 }
25 while (i < mid) aux[k++] = a[i++];
26 while (j < hi) aux[k++] = a[j++];
27 for (int p = lo; p < hi; p++) a[p] = aux[p]; // copy the merged run back
28 }
29
30 public static void main(String[] args) {
31 System.out.println(Arrays.toString(mergeSort(new int[]{4, 1, 3, 2})));
32 }
33}1
2#include <iostream>
3#include <vector>
4using namespace std;
5
6void merge(vector<int>& a, vector<int>& aux, int lo, int mid, int hi) {
7 int i = lo, j = mid, k = lo;
8 while (i < mid && j < hi) {
9 if (a[i] <= a[j]) aux[k++] = a[i++]; // left wins ties, so the sort is stable
10 else aux[k++] = a[j++];
11 }
12 while (i < mid) aux[k++] = a[i++];
13 while (j < hi) aux[k++] = a[j++];
14 for (int p = lo; p < hi; p++) a[p] = aux[p]; // copy the merged run back
15}
16
17void sortRange(vector<int>& a, vector<int>& aux, int lo, int hi) { // sorts a[lo..hi), hi is exclusive
18 if (hi - lo <= 1) return;
19 int mid = lo + (hi - lo) / 2;
20 sortRange(a, aux, lo, mid);
21 sortRange(a, aux, mid, hi);
22 merge(a, aux, lo, mid, hi);
23}
24
25void mergeSort(vector<int>& a) {
26 vector<int> aux(a.size());
27 sortRange(a, aux, 0, (int)a.size());
28}
29
30int main() {
31 vector<int> nums = {4, 1, 3, 2};
32 mergeSort(nums);
33 cout << "[";
34 for (size_t i = 0; i < nums.size(); i++) cout << (i ? ", " : "") << nums[i];
35 cout << "]" << endl;
36}1
2function mergeSort(a) {
3 const aux = new Array(a.length).fill(0);
4 sortRange(a, aux, 0, a.length);
5 return a;
6}
7
8function sortRange(a, aux, lo, hi) { // sorts a[lo..hi), hi is exclusive
9 if (hi - lo <= 1) return;
10 const mid = lo + Math.floor((hi - lo) / 2);
11 sortRange(a, aux, lo, mid);
12 sortRange(a, aux, mid, hi);
13 merge(a, aux, lo, mid, hi);
14}
15
16function merge(a, aux, lo, mid, hi) {
17 let i = lo, j = mid, k = lo;
18 while (i < mid && j < hi) {
19 if (a[i] <= a[j]) aux[k++] = a[i++]; // left wins ties, so the sort is stable
20 else aux[k++] = a[j++];
21 }
22 while (i < mid) aux[k++] = a[i++];
23 while (j < hi) aux[k++] = a[j++];
24 for (let p = lo; p < hi; p++) a[p] = aux[p]; // copy the merged run back
25}
26
27console.log(`[${mergeSort([4, 1, 3, 2]).join(', ')}]`);O(n log n) for best, average and worst case. Splitting halves a segment until length one, which gives about log n levels, and each level merges n elements in total. The splits do not depend on the input order.
Yes, if the merge compares with <= and so takes the left value on equal keys. With < the right value goes first on ties and equal records swap order.
The merge writes into an auxiliary array of length n before copying back, because overwriting the input while reading it would lose values. Add O(log n) for the recursion stack.
Merge sort splits by position and does the work when merging, so it is O(n log n) always and stable but uses O(n) space. Quick sort does the work when partitioning, sorts in place, and is O(n^2) when its splits are lopsided.
No. It makes the same splits and merges for the same segment sizes whatever the order, so there is no O(n) best case. Insertion sort has one.
On an empty array the call SortRange(0, 0) computes mid = 0 and calls itself with the same bounds forever. The check hi - lo <= 1 stops that.