Post
Ask Question

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