1
\$\begingroup\$

Please comment on time and space efficiency.

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{
    [TestClass]
    public class MergeSortUnitTest
    {
        [TestMethod]
        public void MergeTest()
        {
            int[] array = new int[] { 5, 10, 1, 4, 2, 3, 7 };
            SortHalf(array, 0, array.Length-1); 

            int[] expectedOutput = new[] { 1, 2, 3, 4, 5, 7, 10 };
            CollectionAssert.AreEqual(expectedOutput, array);
        }
        private void SortHalf(int[] array, int startIndex, int endIndex)
        {
            int mid;
            if (endIndex > startIndex)
            {
                mid = (endIndex + startIndex) / 2;
                SortHalf(array, startIndex, mid);
                SortHalf(array, mid + 1, endIndex);
                DoMerge(array, startIndex,mid+1, endIndex);
            }
        }

        private void DoMerge(int[] array, int startIndex, int mid, int endIndex)
        {
            int[] temp = new int[array.Length];
            int i, start, numOfElements, position;
            start = mid - 1;
            position = startIndex;
            numOfElements = endIndex - startIndex + 1;
            while((startIndex <= start)&& (mid <= endIndex))
            {
                if(array[startIndex] <= array[mid])
                {
                    temp[position++] = array[startIndex++];
                }
                else
                {
                    temp[position++] = array[mid++];
                }
            }
            while(startIndex <= start)
            {
                temp[position++] = array[startIndex++];
            }

            while(mid <= endIndex)
            {
                temp[position++] = array[mid++];
            }

            for (i = 0; i < numOfElements; i++)
            {
                array[endIndex] = temp[endIndex];
                endIndex--;
            }

        }
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ If anybody's wondering where to get the dll containing Microsoft.VisualStudio.TestTools.UnitTesting you can get it through NuGet \$\endgroup\$
    – jrh
    May 26, 2017 at 22:57

1 Answer 1

4
\$\begingroup\$
  • mid = (endIndex + startIndex) / 2; may overflow. A canonical idiom is

        mid = startIndex + (endIndex - startIndex)/2;
    
  • Allocating (and deallocating) a new temp array in each invocation is a waste of time. Allocate the entire temp once, and pass it down, using same indices as for the actual array. Notice that it also allows to not copying data back from temp to array, which is another waste of time. Instead, ping-pong the arrays' roles.

    Of course, it doesn't affect the asymptotic, but should speed it up twofold.

  • The algorithm looks much more natural with semi-open ranges (that is, end is one after the last element. This will avoid +1 and -1 index corrections, and use < instead of <= to compare indices.

\$\endgroup\$
0

Your Answer

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

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