import java.lang.management.ThreadMXBean;
import java.lang.management.ManagementFactory;
import java.util.Random;
import java.util.Comparator;

class Elt001 {
    int key;   //ソートするキー
    int data;  //ソートが正しく完了しているか検査するためのデータ

    public Elt001(int e1, int e2) {this.key=e1; this.data=e2;}
}


class Cmp001 implements Comparator<Elt001> {
  static int cmp_cnt;       // 比較関数が呼び出された回数をカウントする

  public int compare(Elt001 e1, Elt001 e2) {
      cmp_cnt++;
      return e1.key - e2.key;
  }
}


public class MainTim {
  static int div_val, arr_max, itarate, counter, chk_chk1, chk_chk2;
  static long cpu_time=0;
  static Elt001[] arr0,arr;
  static byte[] chk;
  static ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();

  static void die( String s ) {
    System.err.println("****** error "+s+"********");
    System.exit(0);
  }

  public static void main( String[] args ) { int i;
    if (args.length != 3) die("Usage: main  div_val arr_max itarate");
    div_val = Integer.parseInt(args[0]);
    arr_max = Integer.parseInt(args[1]);
    itarate = Integer.parseInt(args[2]);
    System.err.format("%-7s d=%d  e=%d  R=%d ", "TimSort", div_val, arr_max ,itarate);
    System.out.format("%-7s d=%d  e=%d  R=%d ", "TimSort", div_val, arr_max ,itarate);

    arr0 = new Elt001[arr_max]; for (i=0; i<arr_max; i++) arr0[i]=new Elt001(-1,-1);
    arr  = new Elt001[arr_max];
    chk  = new byte  [arr_max];

    Random random = new Random(div_val + arr_max + 556 ); //乱数の初期化
    Cmp001.cmp_cnt=0;
    for (counter=0; counter<itarate; counter++) {
      System.arraycopy(arr0, 0, arr, 0, arr_max);
      if (div_val == 0 ) for (i = 0; i < arr_max; i++) arr[i].key= 5;                       //一定
      if (div_val == -1) for (i = 0; i < arr_max; i++) arr[i].key= i+1;                     //昇順
      if (div_val == -2) for (i = 0; i < arr_max; i++) arr[i].key= arr_max-i;               //降順
      if (div_val == 1 ) for (i = 0; i < arr_max; i++) arr[i].key= random.nextInt(arr_max); //乱数
      if (div_val >= 2 ) for (i = 0; i < arr_max; i++) arr[i].key= random.nextInt(div_val); //乱数
      if (div_val == -3) {
        for (i = 0; i < arr_max; i++) arr[i].key= i;                          //同値キーがない乱数
        for (i = 0; i < arr_max; i++) {int x=random.nextInt(arr_max);               //ユニーク乱数
                                       int t=arr[i].key; arr[i].key=arr[x].key; arr[x].key=t;
                                      }
      }

      chk_chk1=0;   /*検査のための準備*/
      for (i = 0; i < arr_max; i++) {arr[i].data = i; chk_chk1 += (arr[i].key ^ arr[i].data);}

      long startCpuTime = threadMXBean.getCurrentThreadCpuTime();
      TimSort.sort(arr, 0, arr.length, new Cmp001(), null, 0, 0);
      cpu_time += threadMXBean.getCurrentThreadCpuTime() - startCpuTime;

      /*以下でソートできたことを検査する*/
      for (i = 1; i < arr_max; i++) {
        if ((div_val>=0 ? arr[i-1].key>arr[i].key : arr[i-1].key>=arr[i].key) ||
             (arr[i-1].key==arr[i].key && arr[i-1].data>=arr[i].data) ) {
          if (arr[i-1].key==arr[i].key && arr[i-1].data>=arr[i].data) die(" *** not stable *** ");
          die("not sorted  do_qsort(1)");
        }
      }

      for (i = 0; i < arr_max; i++) chk[i] = 0;
      for (i = 0; i < arr_max; i++) chk[arr[i].data] = 123;
      for (i = 0; i < arr_max; i++) if (chk[i] != 123) die("chk err");

      chk_chk2=0;
      for (i = 0; i < arr_max; i++) {chk_chk2 += (arr[i].key ^ arr[i].data);}
      if (chk_chk1!=chk_chk2) die("chk_chk");
    }

    System.err.format(" cmp=%d  C=%1.2f %n", Cmp001.cmp_cnt, (double)cpu_time/1000000000);
    System.out.format(" cmp=%d  C=%1.2f %n", Cmp001.cmp_cnt, (double)cpu_time/1000000000);
  }
}