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.

advertisement
advertisement

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

Sanfoundry Global Education & Learning Series – 1000 C# Programs.

advertisement
If you wish to look at all C# Programming examples, go to 1000 C# Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.