# Merge sort algorithm

Write a program to demonstrate Merge sort algorithm?

#### Solution

``````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)}");
}

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);
}

}
}
``````