C# Algorithm to merge two sorted arrays without duplicates

You are almost there. You have the main part of the merge algorithm working.

There's just two things left for you to do:

1. Return an array of the correct size. Since you are already tracking the size of the merged array in your k variable, you can use that to resize the array using Array.Resize(ref mergedArray, k);.

2. You want to deduplicate the array. Because you are maintaining the merged array in sorted order, you can check for a duplicate value before you add a new value to the array, and just skip adding it if it is already at the end of the merged array. Note that you must be careful to handle the case where the merged array is currently empty!

Trying to preserve your original code as much as possible, here's one solution.

It introduces a candidate value which we use to check if the value that would be inserted into the result array is already in that array. It also resizes the array to the correct size before returning it:

public static int[] MergeArrays(int[] firstArray, int[] secondArray)
{
    var firstArrayLength  = firstArray.Length;
    var secondArrayLength = secondArray.Length;
    var mergedArray       = new int[firstArrayLength + secondArrayLength];
    var i                 = 0;
    var j                 = 0;
    var k                 = 0;
    int candidate;

    while (i < firstArrayLength && j < secondArrayLength)
    {
        if (firstArray[i] < secondArray[j])
        {
            candidate = firstArray[i];
            i++;
        }
        else
        {
            candidate = secondArray[j];
            j++;
        }

        if (k == 0 || mergedArray[k-1] != candidate)
        {
            mergedArray[k] = candidate;
            k++;
        }
    }

    while (i < firstArrayLength)
    {
        candidate = firstArray[i++];

        if (k == 0 || mergedArray[k-1] != candidate)
        {
            mergedArray[k] = candidate;
            k++;
        }
    }

    while (j < secondArrayLength)
    {
        candidate = secondArray[j++];

        if (k == 0 || mergedArray[k-1] != candidate)
        {
            mergedArray[k] = candidate;
            k++;
        }
    }

    Array.Resize(ref mergedArray, k);
    return mergedArray;
}

You say that you cannot use "array specific" methods. If this precludes the use of Array.Resize() then you could do something like this instead:

int[] result = new int[k];

for (int i = 0; i < k; ++i)
    result[i] = mergedArray[k];

return result;

This more-or-less does what Array.Resize() does - it creates a new array of the correct size and copies the elements of the source array into it.

You might think that you could use Linq to do this using something like

var result = array1.Union(array2).ToArray();

The problem with this is that the result is not sorted, so given

int[] array1 = {1, 3, 5, 7, 9};
int[] array2 = {2, 4, 6, 8, 10};
int[] merged = array1.Union(array2).ToArray();

Console.Write(string.Join(", ", merged));

The output is 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 which is not sorted.

You'd have to add a sorting step:

int[] merged = array1.Union(array2).OrderBy(i => i).ToArray();

But now we've turned an O(N) algorithm into an O(N.Log(N)) one because OrderBy() is O(N.Log(N)). Whether this is actually an issue depends on your circumstances.

Also note that you could also remove duplicates from the array before returning it by returning mergedArray.Distinct().ToArray(), but that introduces an unnecessary extra copy of the data plus an addition O(N) operation. If this is homework, that's probably not what the tutor is looking for!

As a final note, you may notice that there's some repeated code that checks for duplicated values. You could put that code into a local function to avoid repeating it. If you do that, the final method could look something like this:

public static int[] MergeArrays(int[] firstArray, int[] secondArray)
{
    var firstArrayLength  = firstArray.Length;
    var secondArrayLength = secondArray.Length;
    var mergedArray       = new int[firstArrayLength + secondArrayLength];
    var i                 = 0;
    var j                 = 0;
    var k                 = 0;

    void addIfNotDupe(int candidate) // Local function.
    {
        if (k != 0 && mergedArray[k - 1] == candidate)
            return;

        mergedArray[k++] = candidate;
    }

    while (i < firstArrayLength && j < secondArrayLength)
    {
        addIfNotDupe(firstArray[i] < secondArray[j] ? firstArray[i++] : secondArray[j++]);
    }

    while (i < firstArrayLength)
    {
        addIfNotDupe(firstArray[i++]);
    }

    while (j < secondArrayLength)
    {
        addIfNotDupe(secondArray[j++]);
    }

    Array.Resize(ref mergedArray, k);
    return mergedArray;
}