You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
84 lines
2.6 KiB
C#
84 lines
2.6 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
using System.Text;
|
|
|
|
namespace Merge_sort
|
|
{
|
|
class Program
|
|
{
|
|
static void Main(string[] args)
|
|
{
|
|
List<int> unsorted = new List<int>();
|
|
List<int> sorted;
|
|
Random random = new Random();
|
|
Console.WriteLine("Original array elements:" );
|
|
for(int i = 0; i< 10; i++)
|
|
{
|
|
unsorted.Add(random.Next(0,100));
|
|
Console.Write(unsorted[i]+" ");
|
|
}
|
|
Console.WriteLine();
|
|
sorted = MergeSort(unsorted);
|
|
Console.WriteLine("Sorted array elements: ");
|
|
foreach (int x in sorted)
|
|
{
|
|
Console.Write(x+" ");
|
|
}
|
|
Console.Write("\n");
|
|
}
|
|
|
|
|
|
private static List<int> MergeSort(List<int> unsorted)
|
|
{
|
|
if (unsorted.Count <= 1)
|
|
return unsorted;
|
|
List<int> left = new List<int>();
|
|
List<int> right = new List<int>();
|
|
int middle = unsorted.Count / 2;
|
|
for (int i = 0; i < middle; i++) //Dividing the unsorted list
|
|
{
|
|
left.Add(unsorted[i]);
|
|
}
|
|
for (int i = middle; i < unsorted.Count; i++)
|
|
{
|
|
right.Add(unsorted[i]);
|
|
}
|
|
left = MergeSort(left);
|
|
right = MergeSort(right);
|
|
return Merge(left, right);
|
|
}
|
|
|
|
private static List<int> Merge(List<int> left, List<int> right)
|
|
{
|
|
List<int> result = new List<int>();
|
|
while(left.Count > 0 || right.Count>0)
|
|
{
|
|
if (left.Count > 0 && right.Count > 0)
|
|
{
|
|
if (left.First() <= right.First()) //Comparing First two elements to see which is smaller
|
|
{
|
|
result.Add(left.First());
|
|
left.Remove(left.First()); //Rest of the list minus the first element
|
|
}
|
|
else
|
|
{
|
|
result.Add(right.First());
|
|
right.Remove(right.First());
|
|
}
|
|
}
|
|
else if(left.Count>0)
|
|
{
|
|
result.Add(left.First());
|
|
left.Remove(left.First());
|
|
}
|
|
else if (right.Count > 0)
|
|
{
|
|
result.Add(right.First());
|
|
right.Remove(right.First());
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
}
|
|
} |