Merge sort is based on the divide-and-conquer paradigm. We break down an array into two sub arrays. This code sample explains how a merge sort algorithm works and how it is implemented in C#.

Algorithm: Merge Sort

To sort the entire sequence A[1 .. n], make the initial call to the procedure MERGE-SORT (A, 1, n).

MERGE-SORT (A, p, r)

1. IF p < r // Check for base case
2. THEN q = FLOOR[(p + r)/2] // Divide step
3. MERGE (A, p, q) // Conquer step.
4. MERGE (A, q + 1, r) // Conquer step.
5. MERGE (A, p, q, r) // Conquer step.
Here is the code written in C#.

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  6. namespace MergeSort
  7. {
  8. class MergeSort
  9. {
  10. static public void MainMerge(int[] numbers, int left, int mid, int right)
  11. {
  12. int[] temp = new int[25];
  13. int i, eol, num, pos;
  14. eol = (mid - 1);
  15. pos = left;
  16. num = (right - left + 1);
  18. while ((left <= eol) && (mid <= right))
  19. {
  20. if (numbers[left] <= numbers[mid])
  21. temp[pos++] = numbers[left++];
  22. else
  23. temp[pos++] = numbers[mid++];
  24. }
  25. while (left <= eol)
  26. temp[pos++] = numbers[left++];
  27. while (mid <= right)
  28. temp[pos++] = numbers[mid++];
  29. for (i = 0; i < num; i++)
  30. {
  31. numbers[right] = temp[right];
  32. right--;
  33. }
  34. }
  36. static public void SortMerge(int[] numbers, int left, int right)
  37. {
  38. int mid;
  39. if (right > left)
  40. {
  41. mid = (right + left) / 2;
  42. SortMerge(numbers, left, mid);
  43. SortMerge(numbers, (mid + 1), right);
  44. MainMerge(numbers, left, (mid + 1), right);
  45. }
  46. }
  48. static void Main(string[] args)
  49. {
  51. Console.Write("\nProgram for sorting a numeric array using Merge Sorting");
  52. Console.Write("\n\nEnter number of elements: ");
  53. int max = Convert.ToInt32(Console.ReadLine());
  54. int[] numbers = new int[max];
  55. for (int i = 0; i < max; i++)
  56. {
  57. Console.Write("\nEnter [" + (i + 1).ToString() + "] element: ");
  58. numbers[i] = Convert.ToInt32(Console.ReadLine());
  59. }
  60. Console.Write("Input int array : ");
  61. Console.Write("\n");
  62. for (int k = 0; k < max; k++)
  63. {
  64. Console.Write(numbers[k] + " ");
  65. Console.Write("\n");
  66. }
  67. Console.WriteLine("MergeSort By Recursive Method");
  68. SortMerge(numbers, 0, max - 1);
  69. for (int i = 0; i < max; i++)
  70. Console.WriteLine(numbers[i]);
  71. Console.ReadLine();
  72. }
  73. }
  74. }
The output looks like the following: