# Merge sort C# time and space efficiency

Posted on

Problem

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

}
}
}
``````

Solution

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