# Merge Sort optimization

I was looking at other people code and I realized that mine is not so neat after all.

In this version, I included a base case for the merge part (when there is only 2 elements to merge, just sort it normally). I do not know this is a good idea or not, never seen it in other people' codes.

This is the first time I implemented this algorithm. I hope you can help me out with this code so it could look more readable.

class MergeSort
{
public static void Standard() {
int[] A = new int[] {234, 31, 41, 59, 26, 41, 58, 90, 103, 14, 1235, 2134, 12, 673, 234, 234, 64, 23, 132, 432, 123};
int last_Index = A.Length-1;

SplitMerge(A, 0, last_Index);
foreach (int i in A)
Console.Write(i + " ");
}

//Here is the recursive split merge
private static void SplitMerge(int[] A,int iBegin,int iEnd) {
//Base case. Every  recursive has a base case
if (iBegin == iEnd) return;

//Calculate the middle index here. This work for odd number array.
int Middle = (int)Math.Floor((double)(iEnd + iBegin)/2);

//split left
SplitMerge(A, iBegin, Middle);

//split right
SplitMerge(A, Middle+1, iEnd);

//merge left and right
MergeLeftRight(A, iBegin, Middle, iEnd);

}

//This is the merge
private static void MergeLeftRight(int[] A, int iBegin, int iMid, int iEnd) {
//If we are comparing just 2 numbers, just compare them already xD
if (iBegin == iMid) {
int temp_Num = A[iBegin];
if (A[iBegin] >= A[iEnd]) {
A[iBegin] = A[iEnd];
A[iEnd] = temp_Num;
}
return;
}

//Create a temporary list to store numbers
List<int> temp = new List<int> {};

//Declare the last index of left array, we will go to this but will not pass this
int left_End = iMid;

//Same as above. This is for the right array
int right_End = iEnd;

//Left array start from iBegin, but Right array must start fron left_End+1
iMid++;

//Check the number in left and right arrays and sort them while both array still has elements inside
while ((iBegin <= left_End) && (iMid <= right_End)) {
if (A[iBegin] <= A[iMid]) {
iBegin++;
}
else {
iMid++;
}
}

//If right array is empty, add all leftover elements from left array to the list
while (iBegin <= left_End) {
iBegin++;
}

//Same as above loop. Add all leftover elements from right array to the list.
while (iMid <= right_End) {
iMid++;
}

//Put everything back in the original array, merge everything. Since we are going from right to left
//We need to reverse the List.
temp.Reverse();
foreach (int i in temp) {
A[iEnd] = i;
iEnd--;
}
}
}


Since you're asking for a review, here's my input:

• Way too many comments. Comments should say why, not what - the code itself should describe what it's doing.
• Use XML comments to describe methods. // regular comments only work if you're looking at the method's code. When you're using the code, XML comments are picked up by Visual Studio and you get tooltips to help you correctly use the method. For example:

/// <summary>
/// A recursive split merge method.
/// </summary>
/// <param name="A">The array to be sorted.</param>
/// <param name="iBegin">The lower bound index for the sub-array to be sorted.</param>
/// <param name="iEnd">The upper bound index for the sub-array to be sorted.</param>
private static void SplitMerge(int[] A, int iBegin, int iEnd)

• Avoid Hungarian Notation. Prefixing i for int types is useless in .net, and hinders readability. iBegin and iEnd should simply be begin and end to be correct, startIndex and endIndex to be meaningful.

• Use camelCase for parameters and locals. Parameter A should be a... but that's an awfully bad name. unsortedArray, or simply unsorted, would be much more descriptive.

• Avoid snake_case. C# naming conventions don't encourage the use of an underscore (_) in the middle of an identifier's name. Use camelCase for parameters and locals, and PascalCase for types and public members (actually, exposed is more accurate, since internal and protected members should also be PascalCase).

• Avoid Java-style curly braces. Not to start any flamewars, but C# conventions put the opening brace { on the next line.

• Method names should start with a verb. Standard() isn't a good method name. Since it's a member of a class named MergeSort, Sort() would probably be best, and should take the array in as a parameter to be any useful...