import java.util.Random;

class QuicksortProg{
    public static void main(String[] args){
        int len = Integer.parseInt(args[0]);
        int m =5;
        int [] tid = new int[11];

        for(int i = 0; i < m; i++){
            int[] arr = new int[len];
            Random r = new Random();
            for(int j = 0; j < arr.length; j++){
                arr[j] = r.nextInt(len-1);
            }
            long start = System.nanoTime();
            int[] k = new QuicksortCalc().quicksort(arr,0,arr.length-1);
            long timeTakenNS = System.nanoTime() - start;
             tid[i] = (int) (timeTakenNS/1000000.0);
            System.out.println((timeTakenNS/1000000.0)+" ms");
        }
        tid = QuicksortCalc.insertSort(tid,0,m-1);
        System.out.println("Median sorteringstid for " +m+" gjennomlop:"+tid[m/2]+"ms. for n="+len);
    } // end main
} // end class QuicksortProg

class QuicksortCalc{
    int INSERT_LIM = 48;

    /*FUNC*/
    int[] quicksort(int[] a, int left, int right){
        if (right-left < INSERT_LIM){
            return insertSort(a,left,right);
        }else{
            int pivotValue = a[(left + right) / 2];
            swap(a, (left + right) / 2, right);
            int index = left;

            for (int i = left; i < right; i++) {
                if (a[i] <= pivotValue) {
                    swap(a, i, index);
                    index++;
                }
            }
            swap(a, index, right);
            int index2 = index;
            while(index2 > left && a[index2] == pivotValue){
                index2--;
            }

            /*REC*/
            a = quicksort(a, left,  index2);
            /*REC*/
            a = quicksort(a, index + 1, right);
            return a;
        } // end else
    }// end quicksort


	static int[] insertSort(int a[],int left, int right){
		if (left < right){
			int i,k,t;

			for (k = left+1; k <= right; k++){
				t = a[k] ;
				i = k;

				while ( a[i-1]  > t ){
					a[i] = a[i-1];
					if (--i == left) break;
				}
				a[i] = t;
			} // end for k
		}
		return a;
	}// end insertSort


	void swap(int[] array, int left, int right){
		int temp = array[left];
		array[left] = array[right];
		array[right] = temp;
    } // end swap

} // end class QuicksortCalc