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 (l >= r-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 (l >= r-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);
  }

}