Merge Sort

public class MergeSorter {
    
    ///////// "helper" methods //////////
    
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }
    
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void printOrder(Comparable[] b) {
        for (int i = 0; i < b.length; i++) {
            System.out.print(b[i] + "  ");
        }
        System.out.println();
    }

    public static void printIndices(Comparable[] b) {
        for (int i = 0; i < b.length; i++) {
            System.out.print(i + " " + (i < 10 ? " " : ""));
        }
        System.out.println();
        for (int i = 0; i < b.length; i++) {
            System.out.print("---");
        }
        System.out.println();
    }
    
    ///////////////////////////////////////
    
    public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        //copy to aux...
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        
        //merge...
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)                   a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j],aux[i]))  a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }
    }
    
    public static void mergeSort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        
        mergeSort(a, aux, lo, mid);
        mergeSort(a, aux, mid+1, hi);
        
        if ( ! less( a[mid+1], a[mid] ) ) return;  // don't wast time with a merge 
                                                   // if a[] is already in order
        
        merge(a, aux, lo, mid, hi);
        printOrder(a);
    }
    
    public static void mergeSort(Comparable[] b) {
        Comparable[] aux = new Comparable[b.length];
        mergeSort(b, aux, 0, b.length - 1);
    }
    
    public static void main(String[] args) {
        Character[] a = {'K','R','A','T','E','L','E','P','U','I','M','Q','C','X','O','S'};
        
        System.out.println("Order before mergesort application:");
        printOrder(a);
        System.out.println();
        
        printIndices(a);
        mergeSort(a);
        System.out.println();
        System.out.println("Order after mergesort application:");
        printOrder(a);
    }
}

Output

Order before mergesort application:
K  R  A  T  E  L  E  P  U  I  M  Q  C  X  O  S  

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
-----------------------------------------------
A  K  R  T  E  L  E  P  U  I  M  Q  C  X  O  S  
A  K  R  T  E  E  L  P  U  I  M  Q  C  X  O  S  
A  E  E  K  L  P  R  T  U  I  M  Q  C  X  O  S  
A  E  E  K  L  P  R  T  I  U  M  Q  C  X  O  S  
A  E  E  K  L  P  R  T  I  M  Q  U  C  X  O  S  
A  E  E  K  L  P  R  T  I  M  Q  U  C  O  S  X  
A  E  E  K  L  P  R  T  C  I  M  O  Q  S  U  X  
A  C  E  E  I  K  L  M  O  P  Q  R  S  T  U  X  

Order after mergesort application:
A  C  E  E  I  K  L  M  O  P  Q  R  S  T  U  X