class Driver
{
    public static void main (String [] args)
    {
        Sort s1 = null;
         s1.startSort();
         s1.display();
    }
}

public class Sort
{
    private int [] list;
    public static final int MAX = 100;

public void startSort ()
    {
        quick(0, list.length-1);
    }

    private void quick (int first, int last)
    {
        if (first == last)
            return;
        else if ((last - first) == 1)
        {
            if (list[first] > list[last])
            {
                int temp = list[first];
                list[first] = list[last];
                list[last] = temp;
             }
            return;
        }

else if ((last - first) == 2)
        {
            int middle = last - 1;
            sortFirstMiddleLast(first,middle,last);
            return;
        }
    }

private int partition (int first, int last)
    {
        int middle = (first + last) / 2;
        sortFirstMiddleLast(first, middle, last);
      
        swap(middle, last-1);

        int pivotIndex = last-1;
        int pivot = list[pivotIndex];

        int indexFromLeft = first + 1;
        int indexFromRight = last - 2;

        boolean done = false;

while (done == false)
        {
            while (list[indexFromLeft] < pivot)
                indexFromLeft++;
            while (list[indexFromRight] > pivot)
                indexFromRight--;
            if (indexFromLeft < indexFromRight)
            {
                swap(indexFromLeft, indexFromRight);
                indexFromLeft++;
                indexFromRight--;
            }
		     else
            {
			done = true;
            }
       }
       swap(pivotIndex, indexFromLeft);
       pivotIndex = indexFromLeft;
       return pivotIndex;
}

private void sortFirstMiddleLast(int first, int middle, 
                                      int last)
    {
        if (list[first] > list[middle])
            swap(first,middle);
        if (list[middle] > list[last])
            swap(middle,last);
        if (list[first] > list[middle])
            swap(first,middle);
    }

    private void swap (int firstIndex, int secondIndex)
    {
        int temp = list[firstIndex];
        list[firstIndex] = list[secondIndex];
        list[secondIndex] = temp;
    }