MergeSort Algorithm in C# (middle)
class MergeSort
{
public static List<int> Execute(List<int> list)
{
if (list.Count <= 1) { return list; }
//Find the middle point
int middle = list.Count / 2;
var left = new List<int>();
var right = new List<int>();
//Divide the list from the middle
for (int i=0;i<middle;i++)
{
left.Add(list[i]);
}
for (int i=middle;i<list.Count;i++)
{
right.Add(list[i]);
}
//Recursion to keep dividing and sorting.
left = Execute(left);
right = Execute(right);
//This indicates that sorting is done.
if (left[left.Count-1] < right[0])
{
left.AddRange(right);
return left;
}
//If sorting is not done... Merge
var result = Merge(left, right);
return result;
}
private static List<int> Merge(List<int> left, List<int> right)
{
var result = new List<int>();
while (left.Count > 0 && right.Count > 0)
{
//Sort into another list by comparison.
if (left[0] < right[0])
{
result.Add(left[0]);
left.RemoveAt(0);
}
else
{
result.Add(right[0]);
right.RemoveAt(0);
}
}
return result;
}
}
{
public static List<int> Execute(List<int> list)
{
if (list.Count <= 1) { return list; }
//Find the middle point
int middle = list.Count / 2;
var left = new List<int>();
var right = new List<int>();
//Divide the list from the middle
for (int i=0;i<middle;i++)
{
left.Add(list[i]);
}
for (int i=middle;i<list.Count;i++)
{
right.Add(list[i]);
}
//Recursion to keep dividing and sorting.
left = Execute(left);
right = Execute(right);
//This indicates that sorting is done.
if (left[left.Count-1] < right[0])
{
left.AddRange(right);
return left;
}
//If sorting is not done... Merge
var result = Merge(left, right);
return result;
}
private static List<int> Merge(List<int> left, List<int> right)
{
var result = new List<int>();
while (left.Count > 0 && right.Count > 0)
{
//Sort into another list by comparison.
if (left[0] < right[0])
{
result.Add(left[0]);
left.RemoveAt(0);
}
else
{
result.Add(right[0]);
right.RemoveAt(0);
}
}
return result;
}
}
Comments
Post a Comment