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

namespace Qicksort
{
    class Program
    {
        public static void QuickSort(int[] numbers, int left, int right)
        {
            int i = left;
            int j = right;

            int pivot = numbers[(left + right) / 2];
            while (true)
            {
                while (numbers[i] < pivot)
                {
                    i++;
                }
                while (pivot < numbers[j])
                {
                    j--;
                }
                while (i <= j)
                {
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                    i++;
                    j--;
                }
                if (i > j)
                {
                    break;
                }
            }
            if (left < j)
            {
                QuickSort(numbers, left, j);
            }
            if (i < right)
            {
                QuickSort(numbers, i, right);
            }
        }
        static void Main(string[] args)
        {
            Console.WriteLine("Enter lenght of the array: ");
            int lenght = int.Parse(Console.ReadLine());
            int[] numbers = new int[lenght];

            for(int i = 0; i < lenght; i++)
            {
                numbers[i] = int.Parse(Console.ReadLine());
            }

            QuickSort(numbers, 0, numbers.Length - 1);
            Console.WriteLine(string.Join(" ", numbers));
        }
    }
}