Merge Sort:
It takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. In most implementations, it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm.
It takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. In most implementations, it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm.
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace DataStructureAlgoriths
{
class Sort
public void MergeSort()
{
long[] inputArray = new long[] { 4, 9, 8, 6, 3, 2, 1 };
int left = 0;
int right = inputArray.Length - 1;
long [] final =InternalMergeSort(inputArray, left, right);
foreach (var item in final)
{
Console.WriteLine(item);
}
}
private long[] InternalMergeSort(long[] inputArray, int left, int right)
{
int mid = 0;
if (left < right)
{
mid = (left + right) / 2;
InternalMergeSort(inputArray,
left, mid);
InternalMergeSort(inputArray,
(mid + 1), right);
MergeSortedArray(inputArray,
left, mid, right);
}
return inputArray;
}
private void MergeSortedArray(long[] inputArray, int left, int mid, int right)
{
int index = 0;
int total_elements = right - left + 1; //BODMAS rule
int right_start = mid + 1;
int temp_location = left;
long[] tempArray = new long[total_elements];
while ((left <= mid) && right_start <= right)
{
if (inputArray[left] <= inputArray[right_start])
{
tempArray[index++] =
inputArray[left++];
}
else
{
tempArray[index++] =
inputArray[right_start++];
}
}
if (left > mid)
{
for (int j = right_start; j <= right; j++)
tempArray[index++] = inputArray[right_start++];
}
else
{
for (int j = left; j <= mid; j++)
tempArray[index++] =
inputArray[left++];
}
//Array.Copy(tempArray,
0, inputArray, temp_location, total_elements);
// just
another way of accomplishing things (in-built copy)
for (int i = 0, j = temp_location; i < total_elements; i++,
j++)
{
inputArray[j] = tempArray[i];
}
}
}
}
using System;
using System.Collections.Generic;
using System.Text;
namespace DataStructureAlgoriths
{
class Program
{
static void Main(string[] args)
{
Sort s = new Sort();
s.MergeSort();
Console.ReadLine();
}
}
}
No comments:
Post a Comment