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); } }