15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Keep one pointer in each array and repeatedly copy the smaller front value into a new output array. On equal values take the left one, which keeps the merge stable. When one array runs out, copy the rest of the other. The merge takes O(p + q) time and O(p + q) space for the output.
| Time | O(p + q) for arrays of length p and q |
|---|---|
| Head comparisons | At most p + q - 1 |
| Extra space | O(p + q), a new output array; inputs stay unchanged |
| Stable | Yes, when equal values come from the left array first |
| Pointers | L and R read the inputs, O writes the output |
Assume you can recognize an ascending sorted array and have seen a sorting algorithm move values while preserving a sorting contract.
Merge two adjacent sorted runs. A run is a portion that is already sorted. The two runs are separate inputs:
left: an ascending arrayright: an ascending arrayThe result must be:
Stable means that when equal values come from different runs, records from left stay before equal records from right.
Use three indices:
L: current unread position in leftR: current unread position in rightO: next position to fill in the outputNeither input array changes. The algorithm creates a new output array.
Start with these two sorted runs:
1left indices: 0 1 2
2left values: [1, 4, 4]
3
4right indices: 0 1 2
5right values: [2, 4, 5]Create an empty output:
1output: []Set every pointer to index 0.
1L = 0, so left[L] = 1
2R = 0, so right[R] = 2
3O = 0The first unread value of each run is its current head.
12Since 1 < 2, the next output value must be 1.
Write one value at a time. Each choice comes from the smaller current head. If the heads are equal, choose from left.
Merging [1, 4, 4] and [2, 4, 5]: compare the two heads, copy the smaller to the output (ties go left), advance that pointer, and copy the leftover run once one side is empty.
| Step | Left head | Right head | Action | Output | L | R | O |
|---|---|---|---|---|---|---|---|
| Start | 1 | 2 | No value copied yet | [] | 0 | 0 | 0 |
| 1 | 1 | 2 | Take 1 from left | [1] | 1 | 0 | 1 |
| 2 | 4 | 2 | Take 2 from right | [1, 2] | 1 | 1 | 2 |
| 3 | 4 | 4 | Tie: take left 4 | [1, 2, 4] | 2 | 1 | 3 |
| 4 | 4 | 4 | Tie: take left 4 | [1, 2, 4, 4] | 3 | 1 | 4 |
| 5 | exhausted | 4 | Copy right remainder | [1, 2, 4, 4, 4, 5] | 3 | 3 | 6 |
At step 3, suppose the first left 4 is record 4A, and the right 4 is record 4B. Their keys are equal. Taking from the left first produces:
1..., 4A, ...before 4B. The left-first tie rule preserves the order of equal-key records across the two runs.
After step 4, L = 3. That is the length of left, so left is exhausted. Do not read left[L] anymore. The remaining values in right are already sorted:
1right remainder: [4, 5]Copy them in order.
The following invariant holds after each copy:
The output contains the smallest already-selected elements from both runs in sorted order. The unread portions of both input runs remain sorted.
For the example, after output becomes [1, 2, 4]:
[4], still sorted.[4, 5], still sorted.Appending the smaller head is safe because:
left, because left is sorted.right, because right is sorted.When one head is consumed, the remaining part of that run is still a suffix of a sorted array. The remaining run stays sorted.
When one run ends, every remaining value belongs to the other sorted run. Copying that run in order cannot break sorted order.
Use the invariant to choose each action.
0 in both runs.The main loop compares heads only while both heads exist. That boundary check prevents reading beyond an exhausted run.
Input
left: ascending array of values or recordsright: ascending array of values or recordskey(x): returns the comparable key for value or record xReturn
left and rightMutation behavior
leftrightoutput arrayHelper contract
key(x) returns a key that can be compared using <=.key.101 function stableMerge(left, right, key):
202 # Return a new array; do not mutate left or right.
303 output = new array of length length(left) + length(right)
404 L = 0
505 R = 0
606 O = 0
707
808 # Read heads only while both runs have unread values.
909 while L < length(left) and R < length(right):
1010 if key(left[L]) <= key(right[R]):
1111 output[O] = left[L] # Left wins ties for stability.
1212 L = L + 1
1313 else:
1414 output[O] = right[R]
1515 R = R + 1
1616 O = O + 1
1717
1818 # At most one of these loops copies values.
1919 while L < length(left):
2020 output[O] = left[L]
2121 L = L + 1
2222 O = O + 1
2323
2424 while R < length(right):
2525 output[O] = right[R]
2626 R = R + 1
2727 O = O + 1
2828
2929 return outputUse the original inputs:
1left = [1, 4, 4]
2right = [2, 4, 5]
3key(x) = x| Pseudocode line | State |
|---|---|
| 03 | output = [_, _, _, _, _, _] |
| 04 | L = 0 |
| 05 | R = 0 |
| 06 | O = 0 |
Line 09 checks:
1L < length(left) → 0 < 3 → true
2R < length(right) → 0 < 3 → trueBoth heads exist.
Line 10 compares:
1left[L] = left[0] = 1
2right[R] = right[0] = 2
3
41 <= 2 → trueRun lines 11, 12, and 16:
1output[0] = 1
2L = 1
3O = 1State:
1output = [1, _, _, _, _, _]
2L = 1, R = 0, O = 1Line 09 is true because 1 < 3 and 0 < 3.
Line 10 compares:
1left[1] = 4
2right[0] = 2
3
44 <= 2 → falseRun lines 14, 15, and 16:
1output[1] = 2
2R = 1
3O = 2State:
1output = [1, 2, _, _, _, _]
2L = 1, R = 1, O = 2Line 09 is true because 1 < 3 and 1 < 3.
Line 10 compares:
1left[1] = 4
2right[1] = 4
3
44 <= 4 → trueEquality takes the true branch. Run lines 11, 12, and 16:
1output[2] = left[1] = 4
2L = 2
3O = 3State:
1output = [1, 2, 4, _, _, _]
2L = 2, R = 1, O = 3The left 4 was chosen first.
Line 09 is true because 2 < 3 and 1 < 3.
Line 10 compares:
1left[2] = 4
2right[1] = 4
3
44 <= 4 → trueTake the left value. Run lines 11, 12, and 16:
1output[3] = left[2] = 4
2L = 3
3O = 4State:
1output = [1, 2, 4, 4, _, _]
2L = 3, R = 1, O = 4Line 09 now checks:
1L < length(left) → 3 < 3 → falseThe main loop stops. It does not try to read left[3].
Line 19 checks:
1L < length(left) → 3 < 3 → falseThere is no left remainder.
Line 24 checks:
1R < length(right) → 1 < 3 → trueRun lines 25, 26, and 27:
1output[4] = right[1] = 4
2R = 2
3O = 5State:
1output = [1, 2, 4, 4, 4, _]
2L = 3, R = 2, O = 5Line 24 checks again:
12 < 3 → trueRun lines 25, 26, and 27 again:
1output[5] = right[2] = 5
2R = 3
3O = 6State:
1output = [1, 2, 4, 4, 4, 5]
2L = 3, R = 3, O = 6Line 24 now checks 3 < 3, which is false.
Line 29 returns:
1[1, 2, 4, 4, 4, 5]We show that stableMerge returns a sorted, stable output containing exactly the values from both input runs.
Before line 09 runs for the first time:
1output = []
2L = 0
3R = 0No values have been consumed. The empty output is sorted. The unread portions are the complete left and right arrays, which are sorted by the helper contract.
The invariant holds before the loop begins.
Assume the invariant holds at the start of one main-loop iteration.
Both runs have unread heads because line 09 requires:
1L < length(left)
2R < length(right)The head of each run is no larger than every later unread value in that same run because each run is sorted.
If:
1key(left[L]) <= key(right[R])then left[L] is no larger than:
left, because it is the left head;right, because it is no larger than the right head.Appending left[L] is safe because it is the smallest available unread value. Advancing L consumes exactly that head. The unconsumed part of left remains sorted, and right is unchanged and remains sorted.
In the else branch, key(right[R]) < key(left[L]). The right head is no larger than every unread value in right because it is the right head. It is also smaller than the left head and therefore smaller than every unread value in left. Appending right[R] is safe. Advancing R consumes exactly that head. The unconsumed part of right remains sorted, and left remains sorted.
If the keys are equal, line 10 chooses left[L]. An equal-key record from the left run is placed before an equal-key record from the right run. That preserves cross-run equal-key order.
Every main-loop iteration preserves the invariant.
Each main-loop iteration advances exactly one of L or R. Neither pointer can advance beyond its run length, so eventually one run is exhausted.
At that point, the output contains all selected smallest values in sorted order. The other run, if nonempty, is still sorted. Its remaining values are all at least as large as the last chosen values, so copying that remainder in its existing order preserves sorted order.
The two remainder loops copy every unconsumed value exactly once. The returned output contains every input value exactly once and is sorted.
Because equal heads are taken from the left run first, the merge is stable.
Let:
1p = length(left)
2q = length(right)There are exactly p + q output positions. Each placement writes one value and advances either L or R.
L advances at most p times.R advances at most q times.p + q times.The main loop performs a head comparison only while both runs are nonempty. After p + q - 1 placements, at least one run must be exhausted, so there can be at most:
1p + q - 1head comparisons.
The remainder loops perform the remaining placements without comparing heads.
The total time is:
1O(p + q)The algorithm allocates an output array with p + q positions. Its auxiliary space is:
1O(p + q)The input runs are not modified.
Incorrect assumption: “The merge is done when either pointer reaches the end.”
For:
1left = [1]
2right = [2, 3]A broken loop may copy 1, then stop because left is exhausted.
Wrong output:
1[1]Another variation may copy 1, 2 and then stop:
1[1, 2]Both outputs are missing values.
Correction: After the main loop ends, copy the complete nonempty remainder. Here the right remainder is [2, 3], so the correct output is:
1[1, 2, 3]Incorrect line:
1if key(left[L]) < key(right[R]):With this strict comparison, equal keys go to the right branch.
Use tagged records:
1left = [(4, A)]
2right = [(4, B)]The keys are both 4. A right-first tie rule produces:
1[(4, B), (4, A)]That reverses the required cross-run order for equal keys.
Correction: Use <= when deciding whether to take from the left:
1if key(left[L]) <= key(right[R]):The correct stable result is:
1[(4, A), (4, B)]Incorrect assumption: “It is safe to compare both heads until all output cells are filled.”
For:
1left = [1]
2right = [2]After copying 1, L = 1. Reading left[L] now tries to access a missing value.
Correction: Require both pointers to be in bounds before reading either head:
1while L < length(left) and R < length(right):Then use separate remainder loops.
| Input | Correct result | Reason |
|---|---|---|
left = [], right = [1, 2] | [1, 2] | The main loop does not start; copy the right remainder. |
left = [1, 2], right = [] | [1, 2] | The main loop does not start; copy the left remainder. |
left = [1, 1], right = [1, 1] | Four 1 records, with both left records before equal right records | Left-first ties preserve stability. |
left = [5], right = [1, 2, 3] | [1, 2, 3, 5] | The right run can supply several values before the left head is copied. |
Implement:
1stableMerge(left, right)Contract to test:
Executable tests verify empty runs, duplicate counts, and left-first order for tagged equal records.
1
2def stable_merge(left, right):
3 output = [0] * (len(left) + len(right))
4 L = R = O = 0
5 comparisons = 0
6 while L < len(left) and R < len(right): # read heads only while both runs have values
7 comparisons += 1
8 if left[L] <= right[R]: # left wins ties, so the merge is stable
9 output[O] = left[L]
10 L += 1
11 else:
12 output[O] = right[R]
13 R += 1
14 O += 1
15 while L < len(left): # copy whichever remainder is left
16 output[O] = left[L]
17 L += 1
18 O += 1
19 while R < len(right):
20 output[O] = right[R]
21 R += 1
22 O += 1
23 return output, comparisons
24
25merged, comparisons = stable_merge([1, 4, 4], [2, 4, 5])
26print(merged)
27print("head comparisons:", comparisons)1
2import java.util.Arrays;
3
4public class Main {
5 static int comparisons = 0;
6
7 static int[] stableMerge(int[] left, int[] right) {
8 int[] output = new int[left.length + right.length];
9 int L = 0, R = 0, O = 0;
10 while (L < left.length && R < right.length) { // read heads only while both runs have values
11 comparisons++;
12 if (left[L] <= right[R]) output[O++] = left[L++]; // left wins ties, so the merge is stable
13 else output[O++] = right[R++];
14 }
15 while (L < left.length) output[O++] = left[L++]; // copy whichever remainder is left
16 while (R < right.length) output[O++] = right[R++];
17 return output;
18 }
19
20 public static void main(String[] args) {
21 int[] merged = stableMerge(new int[]{1, 4, 4}, new int[]{2, 4, 5});
22 System.out.println(Arrays.toString(merged));
23 System.out.println("head comparisons: " + comparisons);
24 }
25}1
2#include <iostream>
3#include <vector>
4using namespace std;
5
6int comparisons = 0;
7
8vector<int> stableMerge(const vector<int>& left, const vector<int>& right) {
9 vector<int> output(left.size() + right.size());
10 size_t L = 0, R = 0, O = 0;
11 while (L < left.size() && R < right.size()) { // read heads only while both runs have values
12 comparisons++;
13 if (left[L] <= right[R]) output[O++] = left[L++]; // left wins ties, so the merge is stable
14 else output[O++] = right[R++];
15 }
16 while (L < left.size()) output[O++] = left[L++]; // copy whichever remainder is left
17 while (R < right.size()) output[O++] = right[R++];
18 return output;
19}
20
21int main() {
22 vector<int> merged = stableMerge({1, 4, 4}, {2, 4, 5});
23 cout << "[";
24 for (size_t i = 0; i < merged.size(); i++) cout << (i ? ", " : "") << merged[i];
25 cout << "]" << endl;
26 cout << "head comparisons: " << comparisons << endl;
27}1
2function stableMerge(left, right) {
3 const output = new Array(left.length + right.length);
4 let L = 0, R = 0, O = 0;
5 let comparisons = 0;
6 while (L < left.length && R < right.length) { // read heads only while both runs have values
7 comparisons++;
8 if (left[L] <= right[R]) output[O++] = left[L++]; // left wins ties, so the merge is stable
9 else output[O++] = right[R++];
10 }
11 while (L < left.length) output[O++] = left[L++]; // copy whichever remainder is left
12 while (R < right.length) output[O++] = right[R++];
13 return { output, comparisons };
14}
15
16const { output, comparisons } = stableMerge([1, 4, 4], [2, 4, 5]);
17console.log(`[${output.join(', ')}]`);
18console.log(`head comparisons: ${comparisons}`);Do not concatenate them, because that leaves 4 before 2 in [1, 4] + [2, 3]. Compare the two front values, copy the smaller, advance that pointer, and repeat until both arrays are used up.
The version here writes to a new array. If the first array has spare room at its end, fill it from the back, largest value first. That needs no extra array and still runs in O(p + q) time.
O(p + q). Every step writes one output value and advances one pointer, so there are exactly p + q steps. The main loop makes at most p + q - 1 comparisons.
It keeps equal records in input order. With heads (4, A) from the left and (4, B) from the right, taking left gives A before B. Using < instead of <= reverses them.
Sorting the concatenation costs O((p + q) log (p + q)) and ignores that both inputs are already sorted. The merge reads each value once.
The main loop never runs. The matching remainder loop copies the other array as it is, so [] merged with [1, 2] gives [1, 2].