using System;
using System.Collections.Generic;
using System.Linq;

namespace MergeSort
{
  public class Sort 
  {
    public List<int> Msort(List<int> items)
    {
      if (items.Count < 2) {
        return items;
      }
      
      var a = items.Take(items.Count / 2).ToList();
      var b = items.Skip(items.Count / 2).ToList();
      
      return Merge(Msort(a), Msort(b));
    }
    
    private List<int> Merge(List<int> a, List<int> b) 
    {
      var result = new List<int>();
      
      int i = 0, j = 0;
      
      while (i < a.Count && j < b.Count) 
      {
        if (a[i] < b[j]) 
        {
          result.Add(a[i]);
          i++;
        } 
        else 
        {
          result.Add(b[j]);
          j++;
        }
      }
      
      while (i < a.Count) 
      {
        result.Add(a[i]);
          i++;
      }
      while (j < b.Count) 
      {
        result.Add(b[j]);
          j++;
      }
      
      return result;
    }
  }
  
  public class Program
  {
    public static void Main(string[] args)
    {
      var a = new List<int>(){5,1,4,2,3};
      var sort = new Sort();
      Console.WriteLine($"[{string.Join(",",a)}]");
      Console.WriteLine($"[{string.Join(",",sort.Msort(a))}]");
    }
  }
}