MergeSort

Steps:
1. Divide array in to 2 halves.
2. Recursively sort each half.
3. Merge 2 halves.

Complexity: N log N, Mergesort is optimal with respect to # compare operation performed.
Space: Not optimal with respect to space usage.

public class MergeSort {

 private static void merge(Comparable a[], Comparable aux[], int lo,
   int mid, int high) {
  assert isSorted(a, lo, mid);
  assert isSorted(a, mid + 1, high);

  for (int i = lo; i <= high; i++) {
   aux[i] = a[i];
  }

  int index1 = lo;
  int index2 = mid + 1;

  for (int k = lo; k <= high; k++) {
   if (index1 > mid) {// first array integration finished
    a[k] = aux[index2++]; // just copy the second array elements to
          // input array
   } else if (index2 > high) {// second array integration finished
    a[k] = aux[index1++];// just copy the first array elements to
          // input array
   } else if (isLess(aux[index1], aux[index2])) {
    a[k] = aux[index1++];
   } else {
    a[k] = aux[index2++];
   }
  }

  assert isSorted(a, lo, high);
 }

 private static void sort(Comparable[] a, Comparable[] aux, int lo, int high) {

  if (high <= lo)
   return; // return if we reach the minimum array from input for
     // merging

  int mid = lo + (high - lo) / 2;
  sort(a, aux, lo, mid);
  sort(a, aux, mid + 1, high);

  merge(a, aux, lo, mid, high);
 }

 public static void sort(Comparable a[]) {
  Comparable aux[] = new Comparable[a.length];

  sort(a, aux, 0, a.length - 1);
 }

 private static boolean isSorted(Comparable a[], int start, int end) {

  for (int i = start + 1; i < end; i++) {
   if (isLess(a[i], a[i - 1])) {
    return false;
   }
  }

  return true;
 }

 private static boolean isLess(Comparable a, Comparable b) {
  return a.compareTo(b) < 0;
 }
}


/**
 * Merge test code
 */

import java.util.Random;

public class MergeSortTest {
 public static void main(String[] args) {
  System.out.println("MergeSortTest::main()");

  int N = 100;
  Integer[] ipArray = new Integer[N];

  Random random = new Random();

  for (int i = 0; i < ipArray.length; i++) {
   ipArray[i] = random.nextInt(N);
   // System.out.println("MergeSortTest::main() i = "+i+", val = "+ipArray[i]);
  }

  MergeSort.sort(ipArray);

  for (int i = 0; i < ipArray.length; i++) {
   System.out.println("MergeSortTest::main() Sorted ouput i = " + i
     + ", val = " + ipArray[i]);
  }
 }
}