Start learning free

LESSON 230 OF 347 · TWO POINTERS

Merge Sorted Arrays in C#: Two Pointers in O(n + m)

Practice O(n + m) Read the full explanation

Given two sorted arrays of integers, merge them into one sorted array containing all numbers

Example:

Input: first =[1, 4, 8],
       second = [1, 3, 4, 17]

Output: [1, 1, 3, 4, 4, 8, 17]

Note:

Your algorithm should run in O(n + m) time and use O(n + m) extra space.


STEP 1 OF 10
    Ctrl + Enter to check

    C# · TWO POINTERS

    Merge Sorted Arrays in C#, explained

    Problem overview

    The method Merge receives two sorted int[] arrays, first and second, and returns one new sorted array containing every number from both. Duplicates are kept: they are separate elements.

    For first = [1, 4, 8] and second = [1, 3, 4, 17] the result is [1, 1, 3, 4, 4, 8, 17]. Both 1s and both 4s appear, and the output has 3 + 4 = 7 elements.

    The statement asks for O(n + m) time and O(n + m) extra space, where n and m are the lengths of the two arrays. The extra space is the result itself.

    Approach: always take the smaller front element

    The simple way to merge is to copy both arrays into one and sort it. That works, but sorting costs O(k log k) for k = n + m elements, and it ignores the fact that the inputs are already in order.

    Because each array is sorted, its smallest unused element is always at the front of what remains. The smallest unused element overall must therefore be one of the two fronts. Compare them, move the smaller one into the result, and repeat. Each element is moved exactly once, so the work is proportional to n + m.

    To track the fronts, keep one index per array: i for first and j for second. These are the two pointers. A pointer only ever moves forward, and nothing is shifted or deleted.

    Once one array is used up, the other holds only elements that are at least as large as everything already merged, so they can be copied over unchanged.

    Step by step

    1. Create a growable result. The output size is known (n + m), but a List<int> with Add keeps the code simple. An array has a fixed length, so a list is the easier container to fill one element at a time.
    2. Start both pointers at 0. They point to the smallest unused element of each array.
    3. Loop while both arrays still have elements. The condition uses && because the comparison needs a valid element from each side.
    4. Take from first when its element is smaller. Add it to the result and advance i.
    5. Otherwise take from second. This branch also handles equal values. Taking either one first is fine, because equal numbers are interchangeable in the output.
    6. Drain what is left of first. After the main loop, at most one array has elements left. A loop that runs while i < first.Length copies them.
    7. Drain what is left of second, with the matching loop for j. Whichever array was exhausted gives a loop that does nothing.
    8. Convert and return. The method's return type is int[], so ToArray() copies the list into an array.

    The solution in C#

    class Solution {
    public int[] Merge(int[] first, int[] second) {
        List<int> result = new List<int>();
        int i = 0, j = 0;
        while (i < first.Length && j < second.Length) {
            if (first[i] < second[j]) {
                result.Add(first[i]);
                i++;
            } else {
                result.Add(second[j]);
                j++;
            }
        }
        while (i < first.Length) {
            result.Add(first[i]);
            i++;
        }
        while (j < second.Length) {
            result.Add(second[j]);
            j++;
        }
        return result.ToArray();
    }
}

    A few C# details worth noting:

    • Arrays versus lists. first.Length is a property with no parentheses, and the array's size never changes. List<int> has Count and Add and grows as needed. List<T> lives in System.Collections.Generic, which a standalone file must import with a using directive.
    • Declaring two ints at once. int i = 0, j = 0; declares and initializes both variables in one statement.
    • Short-circuit evaluation. In i < first.Length && j < second.Length, both checks run in order, and the loop body is only entered when both hold, so first[i] and second[j] are always valid indices.
    • ToArray() makes a copy. It is a method of List<T>, and the returned array does not share memory with the list. Neither input array is modified.

    Complexity

    Time: O(n + m). Every loop iteration adds one element to the result and advances one pointer. Across the three loops that happens exactly n + m times, and each iteration does constant work. ToArray() copies the n + m elements once more, which stays linear.

    Space: O(n + m). The list and the returned array each hold n + m numbers. Only a few integers beyond that are used.

    Edge cases and common mistakes

    • An empty array. With first empty, the main loop never runs and the second drain loop copies all of second. Merge(new int[0], new[] {2, 5}) returns [2, 5].
    • Arrays that do not overlap. For [1, 2] and [3, 4] the main loop consumes first completely, then the first drain loop does nothing and the second one copies 3, 4. The result is [1, 2, 3, 4].
    • Forgetting the leftovers. Without the two drain loops the result would be missing the tail of one array. This is the most common bug in a merge.
    • Using if instead of while for leftovers. An if would copy only one element.
    • Forgetting to advance a pointer. If i++ or j++ is missing, the same comparison repeats forever.
    • Writing into an array without an index. Arrays have a fixed size and no Add method. If you prefer to fill an int[] of length first.Length + second.Length, you need a third index for the write position.

    Testing

    • first = [1, 4, 8], second = [1, 3, 4, 17] gives [1, 1, 3, 4, 4, 8, 17].
    • first = [], second = [2, 5] gives [2, 5].
    • first = [1, 2], second = [3, 4] gives [1, 2, 3, 4].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free