Merge sort C# time and space efficiency

Question

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--;
            }

        }
    }
}

Answer 1

• 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.