How it works
Two sorted inputs can be merged without sorting their combined contents again. Keep one pointer into each input, compare the next available values, and append the smaller one. The chosen pointer advances, while the other remains ready for the next comparison. Each input element is consumed exactly once.
The sample preserves both copies of three because merging is not deduplication. The result contains every source value in nondecreasing order. If the application also requires unique values, add that as a separate explicit policy rather than accidentally dropping equal elements during an otherwise ordinary merge.
When one input is exhausted, every remaining value in the other input can be appended. Those final loops are essential: forgetting a remainder can produce a plausible sorted prefix while silently losing records. Tests that use only equal-length inputs can miss this bug when both pointers happen to reach the end together.
The less-than-or-equal comparison favors the left source when keys tie. For plain integers that identity is invisible, but for records sorted by a key it defines a stability rule. A generic merge should accept a suitable comparer and document which source takes precedence among equal-comparing elements.
Practice with an empty left input, an empty right input, repeated equal values, and one source whose values are all smaller. Verify two invariants: the result is sorted, and its count equals the sum of source counts. Also compare value frequencies so a duplicated or missing value cannot hide behind a correct total count.
Finally, explain the precondition that both inputs are already sorted under the same ordering rule. The merge uses linear work and storage proportional to the produced result, but it does not detect every ordering mistake by itself. Validate at an appropriate boundary or make the sorted-sequence contract explicit in the surrounding API.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
Console.WriteLine(string.Join(",", Merge(new[] { 1, 3, 5 }, new[] { 2, 3, 6, 7 })));
static List<int> Merge(int[] left, int[] right) {
var result = new List<int>(); int a = 0, b = 0;
while (a < left.Length && b < right.Length) {
if (left[a] <= right[b]) result.Add(left[a++]);
else result.Add(right[b++]);
}
while (a < left.Length) result.Add(left[a++]);
while (b < right.Length) result.Add(right[b++]);
return result;
}
Expected output
1,2,3,3,5,6,7
Once one input is exhausted, the other sorted remainder can be appended directly.