A Simple Merge Sort Implementation [C#]

MergeSort is a "divide and conquer" algorithm that splits an array into two halves (sub arrays) and recursively sorts each sub array before merging them back into one giant, sorted array.
 
In this blog, I will provide a simple implementation of MergeSort with comments on every significant line of code for beginners to quickly grasp the algorithm.
 
Pseudocode

mergeSort(array)
if array.length <= 1 then
return array 
left = new array
right = new array 
mid = left+ right/2
mergeSort(left)
mergeSort(right)
merge(left, right)  
  1. class MergeSort  
  2.     {  
  3.         public static int[] mergeSort(int[] array)  
  4.         {  
  5.             int[] left;  
  6.             int[] right;  
  7.             int[] result = new int[array.Length];  
  8.   
  9.             //As this is a recursive algorithm, we need to have a base case to 
  10.             //avoid an infinite recursion and therfore a stackoverflow  
  11.             if (array.Length <= 1)    
  12.                 return array;  
  13.               
  14.             // The exact midpoint of our array  
  15.             int midPoint = array.Length / 2;  
  16.   
  17.             //Will represent our 'left' array  
  18.             left = new int[midPoint];  
  19.   
  20.             //if array has an even number of elements, the left and right array will have the same number of 
  21.             //elements  
  22.             if (array.Length % 2 == 0)  
  23.                 right = new int[midPoint];  
  24.   
  25.             //if array has an odd number of elements, the right array will have one more element than left
  26.             else  
  27.                 right = new int[midPoint + 1];  
  28.   
  29.             //populate left array  
  30.             for (int i = 0; i < midPoint; i++)  
  31.                 left[i] = array[i];  
  32.   
  33.             //populate right array          
  34.             int x = 0;  
  35.             //We start our index from the midpoint, as we have already populated the left array from 0 to 
  36.             midpont  
  37.             for (int i = midPoint; i < array.Length; i++)  
  38.             {  
  39.                 right[x] = array[i];  
  40.                 x++;  
  41.             }  
  42.   
  43.             //Recursively sort the left array  
  44.             left = mergeSort(left);  
  45.             //Recursively sort the right array  
  46.             right = mergeSort(right);  
  47.             //Merge our two sorted arrays  
  48.             result = merge(left, right);  
  49.   
  50.             return result;  
  51.         }  
  52.   
  53.         //This method will be responsible for combining our two sorted arrays into one giant array  
  54.         public static int[] merge(int[] left, int[] right)  
  55.         {  
  56.             int resultLength = right.Length + left.Length;  
  57.             int[] result = new int[resultLength];  
  58.             //  
  59.             int indexLeft = 0, indexRight = 0, indexResult = 0;  
  60.   
  61.             //while either array still has an element  
  62.             while (indexLeft < left.Length || indexRight < right.Length)  
  63.             {  
  64.                 //if both arrays have elements  
  65.                 if (indexLeft < left.Length && indexRight < right.Length)  
  66.                 {  
  67.                     //If item on left array is less than item on right array, add that item to the result array  
  68.                     if (left[indexLeft] <= right[indexRight])  
  69.                     {  
  70.                         result[indexResult] = left[indexLeft];  
  71.                         indexLeft++;  
  72.                         indexResult++;  
  73.                     }  
  74.                     // else the item in the right array wll be added to the results array  
  75.                     else  
  76.                     {  
  77.                         result[indexResult] = right[indexRight];  
  78.                         indexRight++;  
  79.                         indexResult++;  
  80.                     }  
  81.                 }  
  82.                 //if only the left array still has elements, add all its items to the results array  
  83.                 else if (indexLeft < left.Length)  
  84.                 {  
  85.                     result[indexResult] = left[indexLeft];  
  86.                     indexLeft++;  
  87.                     indexResult++;  
  88.                 }  
  89.                 //if only the right array still has elements, add all its items to the results array  
  90.                 else if (indexRight < right.Length)  
  91.                 {  
  92.                     result[indexResult] = right[indexRight];  
  93.                     indexRight++;  
  94.                     indexResult++;  
  95.                 }  
  96.   
  97.             }  
  98.             return result;  
  99.         }  
  100.     }  
You can now go ahead and call your MergeSort(array) method from Main to see the results.