package sorting;
  
  import java.util.Arrays;
  
  public class Mergesort {
  
    // merge a1[l..m[ and a1[m..r[ into a2[l..r[
    static void merge(int[] a1, int[] a2, int l, int m, int r) {
      int i = l, j = m;
      for (int k = l; k < r; k++)
        if (i < m && (j == r || a1[i] <= a1[j]))
          a2[k] = a1[i++];
        else
          a2[k] = a1[j++];
    }
  
    // recursive, top-down mergesort
    static void mergesortrec(int[] a, int[] tmp, int l, int r) {
      if (r - l <= 1) return;
      int m = l + (r - l) / 2;
      mergesortrec(a, tmp, l, m);
      mergesortrec(a, tmp, m, r);
      if (a[m-1] <= a[m]) return; // optim
      for (int i = l; i < r; i++) tmp[i] = a[i];
      merge(tmp, a, l, m, r);
    }
    
    static void mergesort(int[] a) {
      mergesortrec(a, new int[a.length], 0, a.length);
    }
  
    // exercice : éviter la copie de a vers tmp
    static void mergesort2rec(int[] a, int[] tmp, int l, int r, boolean inplace) {
      if (r - l <= 1) return;
      int m = l + (r - l) / 2;
      mergesort2rec(a, tmp, l, m, !inplace);
      mergesort2rec(a, tmp, m, r, !inplace);
      if (inplace) merge(tmp, a, l, m, r); else merge(a, tmp, l, m, r);
    }
    
    static void mergesort2(int[] a) {
      mergesort2rec(a, Arrays.copyOf(a, a.length), 0, a.length, true);
    }
    
    // bottom-up mergesort
    static void bottomUpMergesort(int[] a) {
      int n = a.length;
      int[] tmp = new int[n];
      for (int len = 1; len < n; len *= 2)
        for (int lo = 0; lo < n-len; lo += 2*len) {
          int mid = lo + len;
          int hi = Math.min(n, mid + len);
          for (int i = lo; i < hi; i++) tmp[i] = a[i];
          merge(tmp, a, lo, mid, hi);
        }
    }
    
    // natural mergesort
    
    // returns hi such that a[lo..hi[ is sorted
    static int findRun(int[] a, int lo) {
      while (++lo < a.length && a[lo-1] <= a[lo]);
      return lo;
    }
    
    static void naturalMergesort(int[] a) {
      int n = a.length;
      if (n <= 1) return;
      int[] tmp = new int[n];
      while (true) {
        for (int lo = 0; lo < n-1; ) {
          // find first run a[lo..mid[
          int mid = findRun(a, lo);
          if (mid == n) { if (lo == 0) return; break; }
          // find second run a[mid..hi[
          int hi = findRun(a, mid);
          // merge
          for (int i = lo; i < hi; i++) tmp[i] = a[i];
          merge(tmp, a, lo, mid, hi);
          lo = hi;
        }
      }
    }
    
    static void merge2(int[] tmp, int[] a, int lo, int mid, int hi) {
      for (int i = lo; i < hi; i++) tmp[i] = a[i];
      merge(tmp, a, lo, mid, hi);
    }
    
    static void naturalMergeSort(int[] t) {
      if(t.length < 2)
        return;
      
      int b = 0;
      int[] bounds = new int[t.length];
      int count = 0;

      while(b < t.length){
        bounds[count] = b;
        count++;
        b = findRun(t, b);    
      }

      if(count < 2)
        return;
      
  //    for (int i = 0; i < count; i++)
  //      System.out.print(bounds[i] + " ");
  //    System.out.println();
  
      int[] tmp = new int[t.length];
      
      for(int len = 1; len < count; len *= 2){
        for(int l = 0; l + len < count; l += 2*len){
          int m = l + len;
          if(m + len < count) {
            merge2(tmp, t, bounds[l], bounds[m], bounds[m+len]);
          } else {
            merge2(tmp, t, bounds[l], bounds[m], t.length);
          }
        }
      }
  }
  
  }
  
  class TestMergesort {
  
    static boolean is_sorted(int[] a) {
      for (int i = 1; i < a.length; i++)
        if (!(a[i - 1] <= a[i]))
          return false;
      return true;
    }
  
    static final int M = 10; // les éléments sont dans 0..M-1
  
    static int[] occurrences(int[] a) {
      int[] occ = new int[M];
      for (int i = 0; i < a.length; i++)
        occ[a[i]]++;
      return occ;
    }
  
    static boolean is_permut(int[] occ1, int[] occ2) {
      for (int i = 0; i < M; i++)
        if (occ1[i] != occ2[i])
          return false;
      return true;
    }
  
    static String print(int[] a) {
      String s = "[";
      for (int i = 0; i < a.length; i++)
        s += (i == 0 ? "" : ", ") + a[i];
      return s + "]";
    }
  
    static int[] random_array(int len) {
      int[] a = new int[len];
      for (int i = 0; i < len; i++)
        a[i] = (int) (M * Math.random());
      return a;
    }
  
    static void test(int[] a) {
      System.out.println("  test with       a = " + print(a));
      int[] occ1 = occurrences(a);
      Mergesort.mergesort2(a);
      int[] occ2 = occurrences(a);
      System.out.println("  mergesort(a) => a = " + print(a));
      if (!is_sorted(a)) {
        System.out.println("FAILURE: not sorted");
        System.exit(1);
      }
      if (!is_permut(occ1, occ2)) {
        System.out.println("FAILURE: elements are different");
        System.exit(1);
      }
    }
  
    public static void main(String[] args) {
      System.out.println("testing mergesort");
      for (int len = 0; len < 10; len++)
        for (int j = 0; j <= len; j++)
          test(random_array(len));
      System.out.println("SUCCESS");
      
      int[] a = new int[50000000];
      //for (int i = 0; i < a.length; i++) a[i] = (5003 * i) % 1000007;
      for (int i = 0; i < a.length; i++) a[i] = -i;
      double start = System.currentTimeMillis();
      Mergesort.naturalMergesort(a);
      System.out.println("BIG");
      System.out.println(System.currentTimeMillis() - start);
    }
  
  }