using System;
using System.Collections.Generic;
namespace HelloWorld
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello world");
            int[] array = new int[]{3, 2, 4, 1, 0};

            Console.WriteLine(String.Join(", ", QuickSort2(array)));


        }
        public static int[] QuickSort(int[] arr)
        {
            if (arr.Length < 2)
            {
                return arr;
            }
            List<int> left = new List<int>();
            List<int> right = new List<int>();
            int pivotindex = arr.Length / 2;
            for (int i = 0; i < arr.Length; i++)
            {
                if (i == pivotindex)
                {
                    continue;
                }
                if (arr[i] > arr[pivotindex])
                {
                    right.Add(arr[i]);
                }
                else
                {
                    left.Add(arr[i]);
                }
            }
            List<int> result = new List<int>();
            result.AddRange(QuickSort(left.ToArray()));
            result.Add(arr[pivotindex]);
            result.AddRange(QuickSort(right.ToArray()));

            return result.ToArray();

        }
        public static int[] QuickSort2(int[] arr)
        {
            if (arr.Length < 2)
            {
                return arr;
            }

            var left = new int[arr.Length / 2 - 1];
            int pivotindex = arr.Length / 2;
            var right = new int[arr.Length - left.Length - 1];
            for (int i = 0; i < arr.Length; i++)
            {
                if (i == pivotindex)
                {
                    continue;
                }
                if (arr[i] > arr[pivotindex])
                {
                    right[i] = arr[i];
                }
                else
                {
                    left[i] = arr[i];
                }
            }
            var result = new int[arr.Length];
            QuickSort2(left);
            QuickSort2(right);
            int filling = 0;
            for (int i = 0; i < left.Length + 1; i++)
            {
                if (i == pivotindex)
                {
                    result[i] = arr[pivotindex];
                }
                else
                {
                    result[i] = left[i];

                }

            }
            for (int i = pivotindex + 1; i < arr.Length; i++)
            {
                result[i] = right[i];
            }


            return result;

        }
    }
}