Write a program to demonstrate Merge sort algorithm?

Solution

For more information about Merge sort refer to the article

using System;
using System.Collections.Generic;

namespace MergeSort
{
    class MergeSort
    {
        static void Main()
        {
            var arr = new[] { 8, 6, 4, 2, 9, 5 };
            SortMerge(arr, 0, arr.Length - 1);

            Console.WriteLine($"Sorted:{string.Join(" ", arr)}");
            Console.ReadLine();
        }

        static void MainMerge(IList<int> arr, int left, int mid, int right)
        {
            var end = mid - 1;
            var currentPos = left;
            var temp = new int[arr.Count];
            var rem = right - left + 1;

            while (left <= end && mid <= right)
            {
                temp[currentPos++] = arr[left] <= arr[mid] ? arr[left++] : arr[mid++];
            }

            while (left <= end)
                temp[currentPos++] = arr[left++];

            while (mid <= right)
                temp[currentPos++] = arr[mid++];

            for (var i = 0; i < rem; i++)
            {
                arr[right] = temp[right];
                right--;
            }
        }

        static void SortMerge(IList<int> arr, int left, int right)
        {
            if (right <= left) return;
            var mid = (right + left) / 2;
            SortMerge(arr, left, mid);
            SortMerge(arr, mid + 1, right);
            MainMerge(arr, left, mid + 1, right);
        }


    }
}