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

Leave a Reply

Your email address will not be published. Required fields are marked *