Post
Ask Question

Merge Sort Algorithm in C#

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;   
  5.   
  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);     
  17.   
  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.         }   
  35.   
  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.         }     
  47.   
  48.         static void Main(string[] args)    
  49.         {    
  50.   
  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: