C# - Sorting Algorithm - Merge Sort Recursive
We often using sorting algorithm to sort numbers and strings. Also we have many sorting algorithms. I have explained here on how merge sort algorithm works in recursive mode.
The recusrive approach requires creatiion multi branch recursion until the elements are comparable by one iterm. The the merging happens with DoMerge function by taking three arguments - start, mid and right.
Click here for C# BubbleSort Algorithm
Click here for C# InsertionSort Algorithm
Click here for C# MergeSort Recursive Algorithm
Click here for C# MergeSort Iterative Algorithm
Click here for C# QuickSort Recursive Algorithm
Click here for C# QuickSort Iterative Algorithm
The complete program and test run output are given below:
Source Code
using System;
using System.Collections.Generic;
using System.Text;
namespace CSharpSort
{
class Program
{
static public void DoMerge(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 MergeSort_Recursive(int [] numbers, int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
MergeSort_Recursive(numbers, left, mid);
MergeSort_Recursive(numbers, (mid + 1), right);
DoMerge(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 By Recursive Method");
MergeSort_Recursive(numbers, 0, len - 1);
for (int i = 0; i < 9; i++)
Console.WriteLine(numbers[i]);
Console.WriteLine(numbers[i]);
}
}
}Output
MergeSort By Recursive Method
1
2
3
4
5
6
7
8
9
Press any key to continue . . .
|