Merge sort C# Implementation

Question

Its been years (10+) since I have worked with sorting algorithms directly. So I have been trying to go over them again to refresh my memory. The thing is my ideas of how to do it doesn't seam to match the way I have the tutorials doing it.

Does it matter? Assuming that my code is working I would almost mean that its correct. However I have also been looking into the Big-O I really cant remember ever seeing this before. I would almost think that if you code it incorrectly it will slow things down and mess up the performance.

public class MergeSort2
    {


        public MergeSort2()
        {
            var data = Util.CreateData.CreateRandomIntArray(200);  // just a method that spits out an array of ints
            var sortedData = Sort(data);

        }


       private int[] copyArray(int[] A, int start, int end)
        {

            int[] result = new int[end-start];

            int cnt = 0;
            for (int i = start; i < end; i++)
            {
                result[cnt] = A[i];
                cnt++;
            }

            return result;
        }


        public int[] Sort(int[] data)
        {

            if (data.Length <= 1)
                return data;

            var length = data.Length / 2;

            int[] LeftArray = copyArray(data,0,length);
            int[] RightArray = copyArray(data, length,data.Length);

            Array.ForEach(data, a => Console.Write(a + ","));
            Console.Write("\r\n");
            Array.ForEach(LeftArray, a => Console.Write(a + ","));
            Console.Write("\t - \t");
            Array.ForEach(RightArray, a => Console.Write(a + ","));
            Console.Write("\r\n");


            RightArray = Sort(RightArray);
            LeftArray = Sort(LeftArray);

            var sorted = merge(RightArray, LeftArray);

            Console.Write("Sorted: ");
            Array.ForEach(sorted, a => Console.Write(a + ","));
            Console.Write("\r\n");

            return sorted;
        }

        public int[] merge(int[] right, int[] left)
        {


            int[] merged = new int[right.Length + left.Length];

            int cntright = 0;
            int cntleft = 0;

            for (int i = 0; i < merged.Length; i++)
            {
                if (cntright == right.Length)
                {
                    merged[i] = left[cntleft];
                    cntleft++;
                }
                else if (cntleft == left.Length)
                {
                    merged[i] = right[cntright];
                    cntright++;
                }
                else if (right[cntright] <= left[cntleft])
                {
                    merged[i] = right[cntright];
                    cntright++;
                }
                else
                {
                    merged[i] = left[cntleft];
                    cntleft++;
                }
            }

            return merged;
        }



    }

So I guess my question is two fold:

1. How is my implementation of merge sort?
2. Does it matter that I'm implementation isn't exactly the same as everyone else?

Answer 1

Advice 1

Since I have very little exposure to C#, I will confine myself to efficiency: you can use double buffer strategy in order to eliminate copyArray, which will increase performance of your mergesort:

public static void coderoddeMergesort(int[] array)
{
    coderoddeMergesort(array, 0, array.Length);
}

public static void coderoddeMergesort(int[] array, int index, int length)
{
    // Do the sanity checks for input. I am not a C# programmer so don't know.
    int[] aux = new int[length];
    Array.Copy(array, index, aux, 0, length);
    coderoddeMergesort(aux, array, 0, index, length);
}

private static void coderoddeMergesort(int[] source,
                                       int[] target,
                                       int sourceOffset,
                                       int targetOffset,
                                       int rangeLength)
{
    if (rangeLength < 2)
    {
        return;
    }

    int middle = rangeLength / 2;

    coderoddeMergesort(target,
                       source,
                       targetOffset,
                       sourceOffset,
                       middle);

    coderoddeMergesort(target,
                       source,
                       targetOffset + middle,
                       sourceOffset + middle,
                       rangeLength - middle);

    coderoddeMerge(source,
                   target,
                   sourceOffset,
                   targetOffset,
                   middle,
                   rangeLength - middle);
}

private static void coderoddeMerge(int[] source,
                                   int[] target,
                                   int sourceOffset,
                                   int targetOffset,
                                   int leftRunLength,
                                   int rightRunLength)
{
    int targetIndex = targetOffset;
    int leftIndex = sourceOffset;
    int leftIndexBound = leftIndex + leftRunLength;
    int rightIndex = leftIndexBound;
    int rightIndexBound = rightIndex + rightRunLength;

    while (leftIndex != leftIndexBound && rightIndex != rightIndexBound)
    {
        target[targetIndex++] =
            source[rightIndex] < source[leftIndex] ?
            source[rightIndex++] :
            source[leftIndex++];
    }

    Array.Copy(source, leftIndex, target, targetIndex, leftIndexBound - leftIndex);
    Array.Copy(source, rightIndex, target, targetIndex, rightIndexBound - rightIndex);
}

Now, I will briefly explain the idea behind the double buffer strategy. You give two arrays to the sorting method. The one is the source array from which we pick elements, and another one is the target array in which we put merged runs.

At the very beginning of sorting (coderoddeMergesort(int[], int, int)) we create an auxiliary buffer aux that contains the exact copy of the range to be sorted. The very first call in coderoddeMergesort(int[], int, int) treats aux as a source array, and array as the target array. For that reason the sorted stuff ends up in the array.

It is very hard to explain formally, but try to think about the fact that we keep alternating the roles of aux and array. And since we have two arrays, we do not need to allocate any more memory: the merge operation merges from source to target. See the following figure:

On random int arrays of length 2 million I get the following results (removed console I/O from your version, of course):

Seed = 636123215194590270
OP mergesort in 2473 milliseconds.
coderodde mergesort in 1767 milliseconds.
Algorithms agree: True.

Advice 2

It would seem from MSDN that the signature of your sorting routine should be:

public static void myFunkyMergesort(int[] array, int startIndex, int length)...

References

If you want to see both your and mine version against each other, you can find everything here.

Hope that helps.

Answer 2

Inside of your copyArray you should not have the cnt variable separate from the for loop, you should just include it in the declaration. The name of that Method should be in PascalCase not in camelCase. You should also give operators some space (ie [end - start])

so this:

   private int[] copyArray(int[] A, int start, int end)
    {

        int[] result = new int[end-start];

        int cnt = 0;
        for (int i = start; i < end; i++)
        {
            result[cnt] = A[i];
            cnt++;
        }

        return result;
    }

would become this

private int[] CopyArray(int[] A, int start, int end)
{
    int[] result = new int[end - start];
    for (int i = start, cnt = 0; i < end; i++, cnt++)
    {
        result[cnt] = A[i];
    }
    return result;
}

you can remove the cnt++ from inside the loop and just add it to the for loop declaration.

---

Variables should be camelCase

 int[] LeftArray = copyArray(data,0,length);
 int[] RightArray = copyArray(data, length,data.Length);

These should be

 int[] leftArray = CopyArray(data,0,length);
 int[] rightArray = CopyArray(data, length,data.Length);

And

public int[] merge(int[] right, int[] left)

should be

public int[] Merge(int[] right, int[] left)

Because Methods should always be in PascalCase

And

int cntright = 0;
int cntleft = 0;

should be

int cntRight = 0;
int cntLeft = 0;

for the same reason

Answer 3

This may seem like a really minor point but try to avoid side effects wherever possible. You want your code to be really obvious to anyone reading it what the main purpose of the code is:

 Array.ForEach(data, a => Console.Write(a + ","));

I look at the code and think that the main purpose is to iterate the array. In fact, the whole reason for the code is writing the array to the console. That can be done like so:

Console.WriteLine(string.Join(",", data));

For the record, I don't even like that as we're doing 2 things in one line.

WriteDataToConsole(data);

...

private static void WriteDataToConsole(int[] data)
{
    var displayString = string.Join(",", data);
    Console.WriteLine(displayString);
}

And then you think, hey - I can write any kind of IEnumerable<T> here! So you change the method to be more generic:

private static void WriteDataToConsole<T>(IEnumerable<T> data)
{
    var displayString = string.Join(",", data);
    Console.WriteLine(displayString);
}

And now you can output a sequence to the console in one line in a really readable way.

Answer 4

How is my implementation of merge sort?

You already have a lot of good advice, so I will focus on something else: coding style.

• Avoid acronyms and abbreviations: cnt should be count
• Avoid Hungarian notation: LeftArray should be Left
• Use var when appropriate
• Use interface instead of class/type when appropriate
• Respect C# Coding Conventions
• Fix your indentation ;)

Also XML documentation would be nice

Does it matter that my implementation isn't exactly the same as everyone else's?

Not really. You may want to check to improve perf, memory, etc. Check in different environments. BenchmarkDotNet should help you.