10
\$\begingroup\$

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?
\$\endgroup\$
7
\$\begingroup\$

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:

Double buffered merge sort

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.

\$\endgroup\$
  • \$\begingroup\$ could you please give more explanation of your advice? I would just like to see a little more review. You have quite a bit of code but almost no explanation of the idea of the double buffer strategy. you also don't explain why the signature should be what you have suggested versus what the OP has. \$\endgroup\$ – Malachi Oct 17 '16 at 14:25
  • 1
    \$\begingroup\$ @Malachi Fair enough. It will take a moment, however. \$\endgroup\$ – coderodde Oct 17 '16 at 14:26
  • \$\begingroup\$ it looks like it will be a wonderful review \$\endgroup\$ – Malachi Oct 17 '16 at 14:27
  • 1
    \$\begingroup\$ @Malachi Done! Thank you for pointing out improvement opportunities! \$\endgroup\$ – coderodde Oct 17 '16 at 14:33
  • 1
    \$\begingroup\$ You sir are amazing. This is exactly what I was after. I have seen this example think its like the one on Wikipedia I just couldn't get my head around why you would want to go that crazy with it when my solution would work just as well. So the point of an algorithm isn't just to get the correct output for the input its to do it at the best speed. I am going to go digest this see if I can get it to work will come back with any questions. \$\endgroup\$ – DaImTo Oct 18 '16 at 7:28
7
\$\begingroup\$

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 it 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

\$\endgroup\$
  • 4
    \$\begingroup\$ you weren't consistent in your naming either, but yes it does (sort of) matter because that is the C# standard for naming variables and methods. just about anywhere you go will require you to name your variables and methods according to this standard. I am curious as to what you mean by using camelCase for 20 years, you would use camelCase for variables, but not for methods or class names and if you had, you should have been consistent in your naming scheme \$\endgroup\$ – Malachi Oct 17 '16 at 13:27
  • 4
    \$\begingroup\$ @DaImTo here's the official MSDN capitalization conventions... You'll find that most of us are picky about that around here :) msdn.microsoft.com/en-us/library/ms229043(v=vs.110).aspx \$\endgroup\$ – RobH Oct 17 '16 at 13:35
  • 1
    \$\begingroup\$ @RobH thanks I found this to msdn.microsoft.com/en-us/library/x2dbyw72(v=vs.71).aspx Pick away. I have become lax and lazy and I am trying to change that. \$\endgroup\$ – DaImTo Oct 17 '16 at 13:36
  • 2
    \$\begingroup\$ Just to be clear, if you have been using Java for the past 20 years, then camelCase is correct for method names. PascalCase is the C# standard though. \$\endgroup\$ – Nate Diamond Oct 18 '16 at 17:26
  • 1
    \$\begingroup\$ Java standards aren't C# standards. In Java public methods are camelCase, not PascalCase. And the curly braces open on the same line in Java and on the next line in C#. \$\endgroup\$ – Mathieu Guindon Oct 18 '16 at 17:37
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Actually the only point of the console writing is because I am visual to understand something completely I like to see what its doing. Now I know you can just use string.join but I personally find Array.foreach sexy any opinion on performance not that it matters when its really just debugging messages. However your last example is awesome I am going to have to steal that one. \$\endgroup\$ – DaImTo Oct 18 '16 at 7:26
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Well I guess that answers another of my questions. I am a big fan of var. However my manager is not. I am keeping my vars. A lot of your comments are me not realizing how "picky" you guys are with code review I will do better next time. \$\endgroup\$ – DaImTo Oct 18 '16 at 12:08
  • 1
    \$\begingroup\$ @DaImTo I think you should use it even more :) \$\endgroup\$ – aloisdg Oct 18 '16 at 14:11
  • \$\begingroup\$ Would you please elaborate a little bit more on your bullet points in the first section? This will make your Review much better. Thanks. \$\endgroup\$ – Malachi Oct 19 '16 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.