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

namespace quick_sort
{
    public static class Extension
    {

        public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> array) where T : IComparable<T>
        {
            List<T> list = array.ToList();

            int left = 0;
            int right = list.Count - 1;

            if (right <= 0)
            {
                return list;
            }

            T pivot = list[right / 2];

            while (left <= right)
            {
                while (list[left].CompareTo(pivot) < 0)
                {
                    ++left;
                }

                while (list[right].CompareTo(pivot) > 0)
                {
                    --right;
                }

                if (left >= right)
                {
                    break;
                }

                T swap = list[left];
                list[left] = list[right];
                list[right] = swap;
            }

            if (left < right)
            {
                return list.Take(right).QuickSort().Concat(list.Skip(right).QuickSort());
            }

            return list;
        }

    }

    internal class Program
    {
        private static void Main(string[] args)
        {
            Console.WriteLine("Enter array with whitespace as delimeter (i.e. 1 2 3):");

            IEnumerable<double> input = Console.ReadLine().Split().Select(double.Parse);
            IEnumerable<double> output = input.QuickSort();

            Console.WriteLine(string.Join(" ", output.Select(x => x.ToString())));

            Console.ReadKey();
        }

    }

}