Tag: algorithms

Merge sort is an algorithm used to sort a collection of items using the divide and conquer paradigm. The algorithm was conceived by John von Neumann in 1945.

The algorithm works by breaking down a list into n sublists until each list has a length of one. This is accomplished by recursively calling a mergeSort function whose task is to identify the middle point of a given list or if there is no middle point return the size one list. Once we have reached the end of a particular branch and have two sublists of size one, the algorithm begins to merge the sublists. These merges will bubble up a sorted list. The function call stack below gives a better picture of this “bubbling up” nature.

Here is an implementation of merge sort with C#. It is based off the C code in GeeksForGeeks.

// Divides a given array in half until length one and then merges
static void mergeSort(int[] arr)
{
   if (arr.Length > 1)
   {
      int middlePoint = arr.Length / 2;
      int[] leftArr = new int[middlePoint];
      int[] rightArr = new int[arr.Length - middlePoint];
      for (int i = 0; i < middlePoint; i++)
      {
         leftArr[i] = arr[i];
      }
      for (int i = 0; i < (arr.Length - middlePoint); i++)
      {
         rightArr[i] = arr[middlePoint + i];
      }
      mergeSort(leftArr);
      mergeSort(rightArr);

      merge(arr, leftArr, rightArr);
   }
}

// Merges to arrays in order
static int[] merge(int[] merged, int[] left, int[] right)
{
   int indexLeft = 0, indexRight = 0, indexMerged = 0;

   while (indexLeft < left.Length && indexRight < right.Length)
   {
      if(left[indexLeft] <= right[indexRight])
      {
         merged[indexMerged] = left[indexLeft];
         indexLeft++;
      }
      else
      {
         merged[indexMerged] = right[indexRight];
         indexRight++;
      }
         indexMerged++;
   }

   while(indexLeft < left.Length)
   {
      merged[indexMerged] = left[indexLeft];
      indexLeft++;
      indexMerged++;
   }

   while (indexRight < right.Length)
   {
      merged[indexMerged] = right[indexRight];
      indexRight++;
      indexMerged++;
   }

   return merged;
}

// Driver
static void Main(string[] args)
{
   int[] myArray = { 5, 22, 1, 2, 45 };
   mergeSort(myArray);
   foreach(int item in myArray)
   {
      Console.Write(item + ","); // 1,2,5,22,45,
   }
}

Below is a function call stack to sort the array [5, 22, 1, 2, 45]. Notice that the algorithm keeps halving the list until both sides are of size 1. Once leftArray and rightArray are of length one, we call the merge function. Due to merge sort’s recursive structure we bubble up merging the sublists into each other. I have used the => symbol to signify the value returned by the function.

mergeSort([5, 22, 1, 2, 45])
mergeSort(leftArray = [5, 22])
	mergeSort(leftArray = [5]) 
	mergeSort(rightArray = [22])
	merge(merged = [5, 22], leftArray = [5], rightArray = [22]) => [5, 22]
mergeSort(rightArray = [1, 2, 45])
	mergeSort(leftArray = [1])
	mergeSort(rightArray = [2, 45])
		megerSort(leftArray = [2]) 
		mergeSort(rightArray = [45]) 
		merge(merged = [2, 45], leftArray = [2], rightArray = [45]) => [2, 45]
	merge(merged = [1, 2, 45], leftArray = [1], rightArray = [2, 45]) => [1, 2, 45]
merge(merged = [5, 22, 1, 2, 45], leftArray = [5, 22], rightArray = [1, 2, 45]) => [1, 2, 5, 22, 45]