﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
	public class MergeSortImplementation
	{
		public static void Run()
		{
			foreach (int value in SortArray(new int[] {5, 2, 3, 1}))
				Console.WriteLine(value);
		}

		public static int[] SortArray(int[] nums)
		{
			return MergeSort(nums);
		}

		public static int[] MergeSort(int[] nums)
		{
			if (nums.Length <= 1)
				return nums;

			// Find half point
			int half = nums.Length / 2;

			// MergeSort Left
			int[] left = new int[half];
			Array.Copy(nums, 0, left, 0, left.Length);
			left = MergeSort(left);

			// MergeSort Right
			int[] right = new int[nums.Length - half];
			Array.Copy(nums, nums.Length - half, right, 0, right.Length);
			right = MergeSort(right);

			// Merge
			return Merge(left, right);
		}

		public static int[] Merge(int[] left, int[] right)
		{
			// Since we can assume the left is sorted, and right is sorted:
			int[] result = new int[left.Length + right.Length];
			int resultIterator = 0;
			int lIterator = 0;
			int rIterator = 0;

			while (lIterator < left.Length || rIterator < right.Length)
			{
				if (lIterator < left.Length && rIterator < right.Length)
				{
					if (left[lIterator] < right[rIterator])
						result[resultIterator++] = left[lIterator++];
					else
						result[resultIterator++] = right[rIterator++];
				}
				else if (lIterator < left.Length && rIterator == right.Length)
					result[resultIterator++] = left[lIterator++];
				else if (rIterator < right.Length && lIterator == left.Length)
					result[resultIterator++] = right[rIterator++];
			}

			return result;
		}
	}
}
