using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var input = new int[5]{10,5,7,3,2};

        Console.WriteLine($"Input: {String.Join(" ", input)}");

        quickSort(input, 0, input.Count-1);

        Console.WriteLine($"Sorded: {String.Join(" ", input)}");

        Console.WriteLine("Hello World");

    }

    static public int Partition(int[] arr, int left, int right) {

         int pivot;

         pivot = arr[left];

         while (true) {

            while (arr[left] < pivot) {

               left++;

            }

            while (arr[right] > pivot) {

               right--;

            }

            if (left < right) {

               int temp = arr[right];

               arr[right] = arr[left];

               arr[left] = temp;

            } else {

               return right;

            }

         }

      }

      static public void quickSort(int[] arr, int left, int right) {

         int pivot;

         if (left < right) {

            pivot = Partition(arr, left, right);

            if (pivot > 1) {

               quickSort(arr, left, pivot - 1);

            }  

            if (pivot + 1 < right) {

               quickSort(arr, pivot + 1, right);

            }

         }

      }

    private static void QuickSort(List<int> values, int left, int right)

    {

        if (left >= right)

            return;

        var pivot = Partition(values, left, right);

        if (pivot > 1)

            QuickSort(values, left, pivot - 1);

        if (pivot + 1 < right)

            QuickSort(values, pivot + 1, right);

    }

    private static int Partition(List<int> values, int left, int right)

    {

        var pivot = values[left];

        while(true)

        {

            // find left

            while (values[left++] < pivot && left <= right)

            {

            }

            // find right

            while (values[right--]> pivot && left <= right)

            {

            }

            if (left < right)

            {

                if (values[left] == values[right])

                    return right;

                Swap(values, left, right);              

            }

            else

            {               

                return right;

            }

        }

        return -1;

    }

    private static void Swap(List<int> values, int leftIndex, int rightIndex)

    {

        var temp = values[leftIndex];

        values[leftIndex] = values[rightIndex];

        values[rightIndex] = temp;

    }

}