using System;
using System.Collections.Generic;
using System.Linq;
class MainClass {
static void Main() {
Console.WriteLine("Hello World!");
int[] test = {8, 5, 6, 89, 12, 10, 100, 15};
var sorted = MergeSort(test);
Console.WriteLine(String.Join(",", sorted));
}
//Merge Sort Start
public static int[] MergeSort(int[] arr)
{
if(arr.Length == 1)
{
return arr;
}
int[] leftArray = null;
if(arr.Length % 2 == 1)
{
leftArray = arr.Take((arr.Length / 2) + 1).ToArray();
}
else
{
leftArray = arr.Take((arr.Length / 2)).ToArray();
}
int[] rightArray = arr.TakeLast(arr.Length / 2).ToArray();
leftArray = MergeSort(leftArray);
rightArray = MergeSort(rightArray);
return MergeArrays(leftArray, rightArray);
}
public static int[] MergeArrays(int[] leftArray, int[] rightArray)
{
int[] output = new int[leftArray.Length + rightArray.Length];
int leftCount = 0;
int rightCount = 0;
int i = 0;
while(leftCount < leftArray.Length || rightCount < rightArray.Length)
{
if(leftCount < leftArray.Length && rightCount < rightArray.Length)
{
int left = leftArray[leftCount];
int right = rightArray[rightCount];
if(left < right)
{
output[i] = left;
leftCount++;
}
else
{
output[i] = right;
rightCount++;
}
}
else if(leftCount < leftArray.Length)
{
output[i] = leftArray[leftCount];
leftCount++;
}
else if(rightCount < rightArray.Length)
{
output[i] = rightArray[rightCount];
rightCount++;
}
i++;
}
return output;
}
//Merge Sort End
public static int[] InsertionSort(int[] arr)
{
for(int i = 1; i < arr.Length; i++)
{
int current = arr[i];
int previousIndex = i-1;
while(previousIndex >=0 && arr[previousIndex] > current)
{
arr[previousIndex+1] = arr[previousIndex];
previousIndex = previousIndex-1;
}
arr[previousIndex+1]=current;
}
return arr;
}
public static int[] SelectionSort(int[] arr)
{
int arrayLength = arr.Length;
for(int i = 0; i < arrayLength; i++)
{
int min = i;
int temp = arr[i];
for(int j = i+1; j < arrayLength; j++)
{
int nextItem = arr[j];
if(arr[j] < arr[min])
{
min = j;
}
}
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}
public static int[] BubbleSort(int[] arr)
{
while(true)
{
bool swapped = false;
for(int i = 0; i < arr.Length-1; i++)
{
int first = arr[i];
int second = arr[i+1];
Console.WriteLine(arr[i+1].GetType());
Console.WriteLine(first.GetType());
if(first > second)
{
arr[i] = second;
arr[i + 1] = first;
swapped = true;
Console.WriteLine(String.Join(",", arr));
}
}
if(!swapped)
{
return arr;
}
}
}
}
