// TRAI_24_t29.java SJ

import java.util.Arrays;
import java.util.Random;

class TRAI_24_t29_skeleton {

    static Random rnd = new Random(System.currentTimeMillis());

    public static void main(String[] args) {

        Random rnd = new Random(System.currentTimeMillis());

        // input size, try with different valus
        int N = 20; // 40000
        if (args.length > 0)
            N = Integer.parseInt(args[0]);

        // print or not
        boolean print = true;
        if (args.length > 1 && (Integer.parseInt(args[1]) > 0))
            print = true;

        // order of elements
        // -1 : descending, 1 = ascending, 0 = random, 2 = randomly one of previous
        int J = 2;
        if (args.length > 2)
            J = Integer.parseInt(args[2]);

        if (J == 2)
            J = randomNumber(rnd, -1, 1);

        if (J == -1) System.out.println("Descending input");
        if (J == 0) System.out.println("Random input");
        if (J == 1) System.out.println("Ascending input");


        Integer[] input;
        long start, end;

        if (N <= 50000) {
            input = makeInput(N, J, 1);
            if (print && N < 50)
                for (int i = 0; i < N; i++)
                    System.out.print(input[i] + " ");
            System.out.println();
            System.out.println("Bubble sort starts");
            start = System.nanoTime();
            bubbleSort(input);
            end = System.nanoTime();
            System.out.println("               " +
                               (end-start) + " ns");
            if (print && N < 50)
                for (int i = 0; i < N; i++)
                    System.out.print(input[i] + " ");
            System.out.println();
        }

        input = makeInput(N, J, 1);
        System.out.println("Merge sort starts");
        start = System.nanoTime();
        mergeSort(input);
        end = System.nanoTime();
        System.out.println("               " +
                (end-start) + " ns");
        if (print && N < 50)
            for (int i = 0; i < N; i++)
                System.out.print(input[i] + " ");
        System.out.println();



        input = makeInput(N, J, 1);
        System.out.println("Quicksort starts");
        start = System.nanoTime();
        quicksort(input);
        end = System.nanoTime();
        System.out.println("               " +
                           (end-start) + " ns");
        if (print && N < 50)
            for (int i = 0; i < N; i++)
                System.out.print(input[i] + " ");
        System.out.println();


    } // main() 

    public static Integer[] makeInput(int N, int J, int seed) {
        Integer[] A = new Integer[N];

        Random r = new Random(seed);
        for (int i = 0; i < N; i++) {
            if (J == 0)
                A[i] = (r.nextInt(N*2));
            else if (J > 0)
                A[i] = (i);
            else
                A[i] = (N-i);
        }

        return A;
    } // makeInput()


    /**
     * Whole array merge sort
     * @param A input array
     * @param <E> element type
     */
    public static <E extends Comparable<? super E>> void mergeSort(E[] A) {
        mergeSort(A, 0, A.length-1);
    }

    /**
     * Subarray merge sort
     * @param A input array
     * @param start start of the subarray
     * @param end end of the subarray
     * @param <E> element type
     */
    public static <E extends Comparable<? super E>> void mergeSort(E[] A, int start, int end) {
        if (start < end) {
            int k = (start + end) / 2;
            mergeSort(A, start, k);
            mergeSort(A, k+1, end);
            merge(A, start, k, end);
        }
    } // mergesort()

    /**
     * Merge of subarrays.
     * Merges reaily sorted subarrays A[start..mid] and A[mid+1..end]
     * into a sorted subarray A[start..end].
     * @param A input array
     * @param start start of the first subarray
     * @param mid end of the first subarray
     * @param end end of the second subarray
     * @param <E> element type
     */
    public static <E extends Comparable<? super E>>void merge(E[] A, int start, int mid, int end) {
        // TODO
    }



    /**
     * Kuplalajittelu.
     * @param A lajiteltava taulukko
     * @param <E> alkiotyyppi
     */
    public static <E extends Comparable<? super E>> void bubbleSort(E[] A) {

        for (int i = 0; i < A.length-1; i++) {
            for (int j = A.length-1; j > i; j--) {
                if (A[j-1].compareTo(A[j]) > 0) {
                    E tmp = A[j-1];
                    A[j-1] = A[j];
                    A[j] = tmp;
                }
            }
        }
    } // bubbleSort()


    public static <E extends Comparable<? super E>>void quicksort(E[] A) {
        quicksort(A, 0, A.length-1);
    }

    public static <E extends Comparable<? super E>>
    void quicksort(E[] A, int i, int j) {
        if (i < j) {
            int k = partition(A, i, j);
            quicksort(A, i, k-1);
            quicksort(A, k+1, j);
        }
    } // quicksort()



    public static <E extends Comparable<? super E>>
    int partition(E[] A, int i, int j) {

        int jakokohta = pivotElement(A, rnd, i, j);
        E jakoalkio = A[jakokohta];
        A[jakokohta] = A[i];

        // toistetaan kunnes i ja j törmäävät
        while (i < j) {

            // etsitään lopusta jakoalkiota pienempi
            while ((i < j) && (jakoalkio.compareTo(A[j]) < 0))
                j--;
            A[i] = A[j];

            // etsitään alusta jakoalkiota suurempi tai yhtäsuuri
            while ((i < j) && (jakoalkio.compareTo(A[i]) >= 0))
                i++;
            A[j] = A[i];

        } // while

        // jakoalkio paikalleen ja palautetaan sijainti
        A[i] = jakoalkio;
        return i;

    } // partition()






    private static <E extends Comparable<? super E>> int pivotElement(E[] A, Random r, int min, int max) {
        int i1 = randomNumber(r, min, max);
        int i2 = randomNumber(r, min, max);
        int i3 = randomNumber(r, min, max);

        if (A[i1].compareTo(A[i2]) < 0) {
            if (A[i2].compareTo(A[i3]) < 0)
                return i2;
            else if (A[i1].compareTo(A[i3]) < 0)
                return i3;
            else
                return i1;
        } else {
            if (A[i1].compareTo(A[i3]) < 0)
                return i1;
            else if (A[i2].compareTo(A[i3]) < 0)
                return i3;
            else
                return i2;
        }
    }






    private static int randomNumber(Random r, int min, int max) {
        int d = max - min + 1;
        if (d < 1)
            d = 1;
       return r.nextInt(d) + min;
    }


} // class