using System;

public class Program

{

    public static void Main()

    {

        int[] numbers = new int[]{6, 5, 8, 10, 15, 4, 6, 2, 1, 12};

        Program.quicksort(numbers, 0, numbers.Length-1);

        foreach (var item in numbers)

        {

            Console.Write(" " + item);

        }

        Console.WriteLine();

    }

    public static void quicksort(int[] arr, int start, int end)

    {

        if (start < end)

        {

            //parition the sublist so that all items less than pivot is on the left and items higher is on the right

            int pivot = Program.partition(arr, start, end);

            quicksort(arr, start, pivot-1);

            quicksort(arr, pivot+1, end);

        }

    }

    //returns the new position of the pivot item

    public static int partition(int[] arr, int start, int end)

    {

        //set pivot to the first item of the sublist

        int pivot = arr[start];

        //set low to point to item to the right of pivot

        int low = start + 1;

        //set high to point to item at the end of the sublist

        int high = end;

        int temp;

        //loop until the low and high points meet/crossover

        while (low < high)

        {

            //move the low pointer until it is pointing to an item greater than the pivot

            while (low <= high && arr[low] <= pivot)

            {

                low++;

            }

            //move the high pointer until it is pointing to an item less than the pivot

            while (low <= high && arr[high] >= pivot)

            {

                high--; 

            }

            //if the pointers have not met or crossed over then swap the values pointed by low & high

            if (low < high)

            {

                temp = arr[high];

                arr[high] = arr[low];

                arr[low] = temp;

            }

        }

        //swap the value at pivot with item at high pointer

        temp = arr[start];

        arr[start] = arr[high];

        arr[high] = temp;

        return high;

    }

}