C# Program to Implement Merge Sort
Posted by Superadmin on August 15 2022 09:37:50

C# Program to Implement Merge Sort

 

This is a C# Program to perform merge sort.

Problem Description

This C# Program Performs Merge Sort.

Problem Solution

A merge sort is a sorting algorithm with complexity of O(nlogn). It is used for sorting numbers, structure, files.

Program/Source Code

Here is source code of the C# Program to Perform Merge Sort. The C# program is successfully compiled and executed with Microsoft Visual Studio. The program output is also shown below.

/*
 *  C# Program to Perform Merge Sort
 */
using System;
using System.Collections.Generic;
using System.Text;
namespace prog
{
    class Program
    {
        static public void mergemethod(int [] numbers, int left, int mid, int right)
        {
            int [] temp = new int[25];
            int i, left_end, num_elements, tmp_pos;
            left_end = (mid - 1);
            tmp_pos = left;
            num_elements = (right - left + 1);
            while ((left <= left_end) && (mid <= right))
            {
                if (numbers[left] <= numbers[mid])
                    temp[tmp_pos++] = numbers[left++];
                else
                    temp[tmp_pos++] = numbers[mid++];
            }
            while (left <= left_end)
                temp[tmp_pos++] = numbers[left++];
            while (mid <= right)
                temp[tmp_pos++] = numbers[mid++];
            for (i = 0; i < num_elements; i++)
            {
                numbers[right] = temp[right];
                right--;
            }
 
        }
        static public void sortmethod(int [] numbers, int left, int right)
        {
          int mid;
          if (right > left)
          {
            mid = (right + left) / 2;
            sortmethod(numbers, left, mid);
            sortmethod(numbers, (mid + 1), right);
            mergemethod(numbers, left, (mid+1), right);
 
          }
        }
        static void Main(string[] args)
 
        {
 
            int[] numbers = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };
            int len = 9;
            Console.WriteLine("MergeSort :");
            sortmethod(numbers, 0, len - 1);
            for (int i = 0; i < 9; i++)
                Console.WriteLine(numbers[i]);
            Console.Read();
         }
   }
}
Program Explanation

This C# program is used to perform merge sort. We have already defined an element in numbers[] array variable. The sortmethod() procedure is used to compute that if the list is of length 0 or 1, then it is already sorted. Otherwise, we are dividing the unsorted list into two sublists of about half the size. Sort each sublist recursively by re-applying merge sort.

Merge the two sublists back into one sorted list. Then we are calling the mergemethod() procedure by passing numbers, left, right and the summation of mid variable value by 1 as an argument. In the function mergesort, provide the list of integers named ‘m’ to the mergesort function in our project.

The result list will have the sorted list which will then return by this function. Check the length of the m list. If the length of the m will equal or less than 1, it means the list is already sorted and we return this list to the calling function.

If the condition is not true, divide the length of the given ‘m’ list by 2. For example, if the length will be of 5 elements, the m will have the value of 2. Similarly, if the elements of m list will be 4 in numbers, then the middle will have the value of 2 as well. Actually, the integer part of the length/2 will be given to the middle 5/2= 2.5 and hence 2 will assign to a middle.

 

We divide the list from this middle into two sublists. Assign the items to the left which are on the left of the middle point of m. Assign the items to the right which is on the right of the middle point of m. By using the recursion at this point, pass the left and right list to the mergesort method and get the sorted list back to these lists.

Runtime Test Cases
 
MergeSort :
1
2
3
4
5
6
7
8
9