9

just a quick note, this is not homework. I'm just trying to brush up on my algorithms. I'm playing around with MergeSort in C# and I've written a recursive method that can sort based on Generics:

class SortAlgorithms
{

    public T[] MergeSort<T> (T[] unsortedArray) where T : System.IComparable<T>
    {
        T[] left, right;
        int middle = unsortedArray.Length / 2;

        left = new T[middle];
        right = new T[unsortedArray.Length - middle];

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

        for (int i = 0; i < middle; i++)
        {
            left[i] = unsortedArray[i];
        }

        for (int i = middle; i < unsortedArray.Length; i++)
        {
            right[i - middle] = unsortedArray[i];
        }

        left = MergeSort(left);

        right = MergeSort(right);


        return Merge<T>(left, right);
    }

    private T[] Merge<T> (T[] left, T[] right) where T : System.IComparable<T>
    {
        T[] result = new T[left.Length + right.Length];

        int currentElement = 0;

        while (left.Length > 0 || right.Length > 0)
        {
            if (left.Length > 0 && right.Length > 0)
            {
                if (left[0].CompareTo(right[0]) < 0)
                {
                    result[currentElement] = left[0];
                    left = left.Skip(1).ToArray();
                    currentElement++;
                }
                else
                {
                    result[currentElement] = right[0];
                    right = right.Skip(1).ToArray();
                    currentElement++;
                }
            }
            else if (left.Length > 0)
            {
                result[currentElement] = left[0];
                left = left.Skip(1).ToArray();
                currentElement++;
            }
            else if (right.Length > 0)
            {
                result[currentElement] = right[0];
                right = right.Skip(1).ToArray();
                currentElement++;
            }
        }

        return result;
    }
}

This works but it is painfully slow. I've used System.Diagnostic.StopWatch to check performance against Array.Sort (which uses QuickSort algorithm) to compare against my MergeSort and the difference is so significant I'm wondering if maybe I'm implementing this wrong. Any comments?

Improve this question
3
  • 1
    Have you read Jons article? msmvps.com/blogs/jon_skeet/archive/2011/01/06/… Commented Aug 27, 2012 at 20:00
  • have you tried the same implementation but without generics? Commented Aug 27, 2012 at 20:01
  • Great answers guys. Sorry it took so long to respond, I've been rewriting the code and I ended up with code that looks almost exactly like what Rafe suggested. Tremendously faster but still much slower than the native Array.Sort. Still playing with it a bit. Commented Sep 1, 2012 at 11:38

4 Answers 4

Reset to default
12

I am not a C# programmer, but could the problem be the use of statements like this one?

left = left.Skip(1).ToArray();

This might be implemented in a way that forces a deep copy of the underlying array. If so, this would drop the performance of merge from O(n) to O(n2), immediately dropping the performance of the resulting merge sort from O(n log n) to O(n2).

(This is because the recurrence changes from

T(1) = O(1)

T(n) ≤ 2T(n / 2) + O(n)

which has solution T(n) = O(n log n), to

T(1) = O(1)

T(n) ≤ 2T(n / 2) + O(n2)

which has solution T(n) = O(n2).)

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

It doesn't implement a deep copy, but it does cause creation of a new array (with a shallow copy) .. not sure how it changes the bounds, but it is still not ideal.
@pst- If this creates a new array and shallow-copies the elements over, this would also cause the performance drop, since the shallow copy still takes O(n) time to make.
Thanks for the clarification, I wasn't sure if it was an aspect of being a deep copy or not.
+1. I don't think ToArray() is needed at all - removing ToArray call and making left/right to be IEnumerator (with manual Current/MoveNext calls) would make code faster and keep its fancy LINQ's feel.
@AlexeiLevenkov It's "needed" here because of how the method is currently setup (however, I would agree this is the problem ;-). Generally though, one would pass the same array with a virtual left/right split (e.g. C-style implementation) or use something like ArraySegment.
2

You are constantly allocating memory in the form of intermediate arrays. Think in the direction of reusing the original array.

Improve this answer

Comments

1

As the other two answers have said, you're creating new arrays all over the place, spending lots of time and memory on that (I'd guess, most of your time and almost all of your memory use).

Onto that again, I'd add that all else being equal recursion tends to be slower than iteration, and use more stack space (perhaps even causing overflow with a big enough problem, where iteration would not).

However. Merge-sort lends itself well to multi-threaded approach, because you can have different threads handle different parts of first batch of partitioning.

Hence, if it were I playing with this, my next two experiments would be:

  1. For the first bit of the partitioning, instead of calling MergeSort recursively, I'd launch a new thread until such a time as I had a thread per core running (whether I should do it per physical core or virtual core in the case of hyperthreading, is itself something I'd experiment with).
  2. That done, I'd try re-writing the recursive method to do the same thing without recursive calls.

After the ToArray() matter was dealt with, seeing how a multi-threaded approach that first split the work among an optimal number of cores, and then had each core do its work iteratively, could be quite interesting indeed.

Improve this answer

7 Comments

Rather than dealing with whether or not to spawn a new thread, you can just create a new Task and let it all go into a thread pool. The thread pool will likely be sized to about the number of physical processors.
In my experience, merge sort (albeit on the JVM on Windows) "works best" with about 1.5-2 max threads per core on an iCore 5/7 series (don't underestimate process stealing ;-). Also, threads should not be used for a small n (the leaves and edge brancges) and switching to a non-merge sort for the edges is a "common optimization" ..
@JonHanna Physical (virtual?) core. The i5 doesn't have hyper-threading. Not exactly sure all the factors that applied, but there is an advantaged of limiting the number of spawned threads to some "reasonably small" ratio of what the hardware can natively handle (with thread pool/recycling preferably).
@Servy there are advantages in keeping neighbouring partitions in the hands of the same thread though, which hitting a fixed number of threads would give more easily than creating new tasks unless you had a limit below which the task switched to finishing the job rather than creating yet more tasks. Just where the optimum point lay would be an interesting thing in itself.
@JonHanna That would indeed be interesting.
|
0

First off, here's a link to a streamlined solution to a similar question: Java mergesort, should the "merge" step be done with queues or arrays?

Your solution is slow because you're repeatedly allocating new subarrays. Memory allocation is way more expensive than most other operations (you have allocation cost, collection cost, and loss of cache locality). Normally it isn't an issue, but if you're trying to code a tight sorting routine, then it matters. For merge sort, you only require one destination array and one temporary array.

Forking threads to parallelise is still orders of magnitude more expensive than that. So don't fork unless you have a massive amount of data to sort.

As I mention in the answer above, one way to speed up your merge sort is to take advantage of existing order in the input array.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.