Merge Sort
by Isai Damier, Android Engineer @ Google

/*****************************************************************************
 * Author: Isai Damier
 * Title: Mergesort
 * Project: geekviewpoint
 * Package: algorithm.sorting
 *
 * Statement:
 *   Given a disordered list of integers (or any other items),
 *   rearrange the integers in natural order.
 *
 * Sample Input: {8,5,3,1,9,6,0,7,4,2,5}
 *
 * Sample Output: {0,1,2,3,4,5,5,6,7,8,9}
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n*log(n)).
 *
 * Approach:
 *   Merge sort is a divide and conquer algorithm. In the divide and conquer
 *   paradigm, a problem is broken into pieces where each piece still retains
 *   all the properties of the larger problem -- except its size. To solve
 *   the original problem, each piece is solved individually; then the pieces
 *   are merged back together.
 *
 *   For illustration, imagine needing to sort an array of 200 elements using
 *   selection sort. Since selection sort takes O(n^2), it would take about
 *   40,000 time units to sort the array. Now imagine splitting the array
 *   into ten equal pieces and sorting each piece individually still using
 *   selection sort. Now it would take 400 time units to sort each piece;
 *   for a grand total of 10*400 = 4000. Once each piece is sorted, merging
 *   them back together would take about 200 time units; for a grand total of
 *   200+4000 = 4,200. Clearly 4,200 is an impressive improvement over
 *   40,000. Now imagine greater. Imagine splitting the original array into
 *   groups of two and then sorting them. In the end, it would take about
 *   1,000 time units to sort the array. That's how merge sort works.
 ****************************************************************************/ 
 private void mergesort(int[] input, int first, int last) {
  // break problem into smaller structurally identical pieces
  int mid = (first + last) / 2;
  if (first < last) {
    mergesort(input, first, mid);
    mergesort(input, mid + 1, last);
  }
  // merge solved pieces to get solution to original problem
  int a = 0, f = first, l = mid + 1;
  int[] tmp = new int[last - first + 1];

  while (f <= mid && l <= last) {
    tmp[a++] = input[f] < input[l] ? input[f++] : input[l++];
  }
  while (f <= mid) {
    tmp[a++] = input[f++];
  }
  while (l <= last) {
    tmp[a++] = input[l++];
  }
  a = 0;
  while (first <= last) {
    input[first++] = tmp[a++];
  }
}

import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {
  
  @Test
  public void testMergesort() {
    System.out.println(""mergesort"");
    int[] input = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
    Sorting instance = new Sorting();
    instance.mergesort(input);
    for (int i = 1; i < input.length; i++) {
      if (input[i - 1] > input[i]) {
        fail(""mergesort method fails."");
      }
    }
  }
}