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

namespace CV07
{
    class Program
    {

        static int len = 10000000;

        static void QuickSort_lr(int[] p, int l, int r)
        {
            if (l >= r) return;
            var pivot = (l + r) / 2;

            //menší přesunu před pivot, větší za pivot
            var i = l;
            var j = r;
            var v = p[pivot];

            while (i <= j)
            {
                while (p[i] < v) i++; //hledám chybu zleva
                while (p[j] > v) j--; //hledám chybu zprava
                if (i > j) break; //test na ukončení opakování
                //spravím chyby tj. prohodím p[i] s p[j]
                var x = p[i];
                p[i] = p[j];
                p[j] = x;
                i++;
                j--;
            }

            QuickSortP_lr(p, l, j);
            QuickSortP_lr(p, i, r);
        }

        static void QuickSort(int[] p)
        {
            QuickSort_lr(p, 0, p.Length - 1);
        }

        static void QuickSortP_lr(int[] p, int l, int r)
        {
            if (l >= r) return;
            var pivot = (l + r) / 2;

            //menší přesunu před pivot, větší za pivot
            var i = l;
            var j = r;
            var v = p[pivot];

            while (i <= j)
            {
                while (p[i] < v) i++; //hledám chybu zleva
                while (p[j] > v) j--; //hledám chybu zprava
                if (i > j) break; //test na ukončení opakování
                //spravím chyby tj. prohodím p[i] s p[j]
                var x = p[i];
                p[i] = p[j];
                p[j] = x;
                i++;
                j--;
            }

            if (r - l > len - 1000000)
            {
                Parallel.Invoke(
                () => QuickSortP_lr(p, l, j),
                () => QuickSortP_lr(p, i, r)
                );
            }
            else
            {
                QuickSortP_lr(p, l, j);
                QuickSortP_lr(p, i, r);
            }
        }

        static void QuickSortP(int[] p)
        {
            QuickSortP_lr(p, 0, p.Length - 1);
        }

        static void Main(string[] args)
        {

            Random r = new Random();

            int[] arr = new int[len];
            int[] arrParallel = new int[len];

            for (int i = 0; i < len; i++)
            {
                arr[i] = arrParallel[i] = r.Next() % len + 1;
            }

            Stopwatch stopwatch = Stopwatch.StartNew();
            QuickSort(arr);
            stopwatch.Stop();
            Console.WriteLine("Normal:\t\t" + stopwatch.ElapsedMilliseconds);

            Stopwatch stopwatchParallel = Stopwatch.StartNew();
            QuickSortP(arrParallel);
            stopwatchParallel.Stop();
            Console.WriteLine("Parallel:\t" + stopwatchParallel.ElapsedMilliseconds);

            Console.Read();

        }
    }
}