Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with sub problems, we state each sub problem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through sub problems.
Algorithm: Merge Sort
To sort the entire sequence A[1 .. n], make the initial call to the procedure MERGE-SORT (A, 1, n).
MERGE-SORT (A, p, r)
1. IF p < r // Check for base case
2. THEN q = FLOOR[(p + r)/2] // Divide step
3. MERGE (A, p, q) // Conquer step.
4. MERGE (A, q + 1, r) // Conquer step.
5. MERGE (A, p, q, r) // Conquer step.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MergeSort
{
class MergeSort
{
static public void MainMerge(int[] numbers, int left, int mid, int right)
{
int[] temp = new int[25];
int i, eol, num, pos;
eol = (mid - 1);
pos = left;
num = (right - left + 1);
while ((left <= eol) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
temp[pos++] = numbers[left++];
else
temp[pos++] = numbers[mid++];
}
while (left <= eol)
temp[pos++] = numbers[left++];
while (mid <= right)
temp[pos++] = numbers[mid++];
for (i = 0; i < num; i++)
{
numbers[right] = temp[right];
right--;
}
}
static public void SortMerge(int[] numbers, int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
SortMerge(numbers, left, mid);
SortMerge(numbers, (mid + 1), right);
MainMerge(numbers, left, (mid + 1), right);
}
}
static void Main(string[] args)
{
Console.Write("\nProgram for sorting a numeric array using Merge Sorting");
Console.Write("\n\nEnter number of elements: ");
int max = Convert.ToInt32(Console.ReadLine());
int[] numbers = new int[max];
for (int i = 0; i < max; i++)
{
Console.Write("\nEnter [" + (i + 1).ToString() + "] element: ");
numbers[i] = Convert.ToInt32(Console.ReadLine());
}
Console.Write("Input int array : ");
Console.Write("\n");
for (int k = 0; k < max; k++)
{
Console.Write(numbers[k] + " ");
Console.Write("\n");
}
Console.WriteLine("MergeSort By Recursive Method");
SortMerge(numbers, 0, max - 1);
for (int i = 0; i < max; i++)
Console.WriteLine(numbers[i]);
Console.ReadLine();
}
}
}
![]()