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