Merge Sort

Hi guys on this page we will be looking at the MergeSort. The merge sort is a quick and efficient algorithm to sort arrays.

The Merge Sort is a two stage algorithm, in simple terms if we started of with an array of jumbled up numbers the list would be successivley divided in half, forming two sublists until each sublist is of length one. In the second stage each pair of sublists is repeatedly merged to produce new sorted sublists until there is only one sublist remaining. As each pair of lists is merged they are merged together in order. In which case merging the two final sublists would result in one final sorted array.

Completed Merge sort example

Here below is the completed MergeSort in C# and I will hope to provide a simple implementation of MergeSort with comments on significant lines of code for beginners to quickly grasp the algorithm.

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

Example by Benjamin Adebowale.

 

.