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

namespace ConsoleApp1
{
    class Program
    {

        static void quickSort(int[] array, int left, int right)
        {
            if (left >= right)
            {
                return;
            }

            int l, r;
            l = left;
            r = right;

            int pivot = array[(left + right) / 2];

            while(l <= r)
            {
                while (array[l] < pivot) l++;
                while (array[r] > pivot) r--;
                if (l <= r)
                {
                    int c = array[l];
                    array[l] = array[r];
                    array[r] = c;
                    l++;
                    r--;
                }
            }
            quickSort(array, left, r);
            quickSort(array, l, right);

        }


        static void mergeSort(int[] array, int left, int right)
        {
            if (left >= right)
            {
                return;
            }
            else
            {
                // 1. Разбить на подмассивы
                int mid = (left + right) / 2;
                // 2. Сортировать подмассивы
                mergeSort(array, left, mid);
                mergeSort(array, mid + 1, right);
                // 3. Объединение массивов
                mergeArray(array, left, mid, right);
            }

        }

        private static void mergeArray(int[] array, int left, int mid, int right)
        {
            int[] temp = new int[right - left + 1];
            int i = left;
            int j = mid + 1;
            int k = 0;

            while (i <= mid && j <= right) { 
                if (array[i] < array[j])
                {
                    temp[k] = array[i];
                    i++;
                    k++;
                }
                else
                {
                    temp[k] = array[j];
                    j++;
                    k++;
                }
             }
            while(i <= mid) {
                temp[k] = array[i];
                i++;
                k++;
            }
            while (j <= right)
            {
                temp[k] = array[j];
                j++;
                k++;
            }

            for (int m = 0; m < temp.Length; m++)
            {
                array[left + m] =  temp[m];
            }


        }

        static int max(int[] array, int left, int right)
        {
            if (left == right)
            {
                return array[left];
            }
            else if (left == right-1)
            {
                return (array[left] > array[right]) ? array[left] : array[right];
            }
            else
            {
                int mid = (left + right) / 2;
                int m1 = max(array, left, mid);
                int m2 = max(array, mid+1, right);
                return max(new int[] {m1, m2 }, 0, 1);
            }
        }



        static int sum (int [] array, int first)
        {

            if (first > array.Length - 1)
            {
                return 0;
            }
            else if(first == array.Length-1)
            {
                return array[0];
            }
            else
            {
                return array[first] + sum(array, first+1) ;
            }
        }


        static void Main(string[] args)
        {
            int[] array = new int[] { 11, 5, 2, 4, 6, 7 };

            quickSort(array, 0, array.Length - 1);
            foreach (int value in array)
            {
                Console.Write(value + " ");
            }
            
            //Console.WriteLine(max(array, 0, array.Length-1));
           
        }
    }
}
