package com.varunvats.practice.sorting;

public class MergeTopDown extends MergeBase {

    public static <T extends Comparable<T>> void sort(T[] a) {
        final int N = a.length;
        aux = new Comparable[N];
        sort(a, 0, N - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] a, int low, int high) {
        if (low >= high)
            return;
        final int mid = (low + high) / 2;
        sort(a, low, mid);
        sort(a, mid + 1, high);
        if (!less(a[mid], a[mid + 1]))
            merge(a, low, mid, high);
    }

}

package com.varunvats.practice.sorting;

public class MergeTopDown extends MergeBase {

    public static <T extends Comparable<T>> void sort(T[] a) {
        final int N = a.length;
        aux = new Comparable[N];
        sort(a, 0, N - 1);
    }

    private static <T extends Comparable<T>> void sort(T[] a, int low, int high) {
        if (low >= high)
            return;
        final int mid = (low + high) / 2;
        sort(a, low, mid);
        sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }

}

--- 
+++ 
@@ -14,7 +14,8 @@
         final int mid = (low + high) / 2;
         sort(a, low, mid);
         sort(a, mid + 1, high);
-        merge(a, low, mid, high);
+        if (!less(a[mid], a[mid + 1]))
+            merge(a, low, mid, high);
     }
 
 }
Optimize merge step of Merge sort.

A merge is necessary only when the last element of the sorted left
sub-array is greater than or equal to the first element of the sorted
right sub-array.
