import java.util.*;

class TimingMergeSort
{
	public static void swap(int[] data, int x, int y)
	{
		int temp = data[x];
		data[x] = data[y];
		data[y] = temp;
	}
	
	public static void merge(int[] data, int left, int mid, int right)
	{
		int[] A;
		A = new int[mid-left+2];

		int[] B;
		B = new int[right-mid+1];

		int i;

		// Copy the first half into A
		for(i = left; i <= mid; i++)
			A[i-left] = data[i];

		// Place infinity in the last slot of A
		A[A.length-1] = Integer.MAX_VALUE;

		// Copy the second half into B
		for(i = mid+1; i <= right; i++)
			B[i-(mid+1)] = data[i];

		// Place infinity in the last slot of B
		B[B.length-1] = Integer.MAX_VALUE;
		
		i = 0;		// index for A
		int j = 0;	// index for B
		int l;

		// A and B are merged back into data
		for(l = left; l <= right; l++)
		{
			if(A[i] <= B[j])
			{
				data[l] = A[i];
				i++;
			}
			else
			{
				data[l] = B[j];
				j++;
			}
		}		


	}

	public static void recursiveMergeSort(int[] data, int left, int right)
	{
		if (left < right)
		{
			int mid = (left + right)/2;
			recursiveMergeSort(data, left, mid);
			recursiveMergeSort(data, mid+1, right);
			merge(data, left, mid, right);
		}
	}

	public static void mergeSort(int[] data, int n)
	{
		recursiveMergeSort(data, 0, n-1);
	}
	
	public static void main(String[] args)
	{
		long time, newTime, sum;

                System.out.print("{");
                for(int n = 1000; n <= 20000; n=n+1000)
                {
			sum = 0;
			for (int j = 0; j < 100; j++)
			{
                        	// Generate a random integer array of size n
                        	int[] data;
                        	data = new int[n];

                        	// Random is a java class defined in java.util     
                        	// To learn more about this class see 
                        	// http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html
                        	Random rand;
                        	rand = new Random();

                        	for(int i = 0; i < n; i++)
                                	data[i] = rand.nextInt();

                        	// Initialize time to the value before calling
                        	// bubbleSort and newTime to the value after
                        	time = System.currentTimeMillis();
                        	mergeSort(data, n);
                        	newTime  = System.currentTimeMillis();

				sum = sum + (newTime-time);

			}

                        if(n < 20000)
                                System.out.print(sum*1.0/100+", ");
                        else
                                System.out.println(sum*1.0/100+"}");
                }


	}
}