In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and von Neumann as early as 1948.
using System;
namespace MergeSort
{
class Program
{
private static void PrintArray(int[] arr)
{
for(int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
private static void Merge(int[] arr, int start, int mid, int end)
{
int[] temp = new int[arr.Length];
int i = start;
int j = mid;
int k = 0;
while(i<mid && j < end)
{
if (arr[i] < arr[j])
{
temp[k] = arr[i];
i++;
k++;
}
else
{
temp[k] = arr[j];
j++;
k++;
}
}
while (i < mid)
{
temp[k] = arr[i];
k++;
i++;
}
while( j < end)
{
temp[k] = arr[j];
k++;
j++;
}
for(int x = start, y=0; x < end; x++,y++)
{
arr[x] = temp[y];
}
}
private static void MergeSortUtil(int[] arr, int start, int end)
{
if (end > start)
{
int mid = (start + end) / 2;
MergeSortUtil(arr, start, mid);
MergeSortUtil(arr, mid + 1, end);
Merge(arr, start, mid, end);
}
}
private static void MergeSort(int[] arr)
{
MergeSortUtil(arr, 0, arr.Length);
}
static void Main(string[] args)
{
int[] arr = new int[]{ 4, 7, 2, 8, 1, 9, 3, 5, 6 };
PrintArray(arr);
MergeSort(arr);
PrintArray(arr);
}
}
}
This is using divide and conquer approach and Time Complexity of the above solution is O(nlogn).
