An example of merge sort in Java. This is not an in-place sort.

gistfile1.java

/**
 * A demonstration of Merge Sort in Java.
 */
public class Merge {
  
	public Merge() {}
	
	/**
	 * Gets a sorted array in O(n log n).
	 * 
	 * @param arr - the array to sort
	 * @return int[] the sorted array
	 */
	public int[] sort(int[] arr) {
		int[] result;
		if (arr.length == 1) {
			result = arr;
		} else {
			int[] l = left(arr);
			int[] r = right(arr);
			result = merge(sort(l), sort(r));
		}
		return result;
	}
	
	/**
	 * Merges two sorted arrays.
	 * 
	 * @param left
	 * @param right
	 * @return int[] the merged array
	 */
	private int[] merge(int[] left, int[] right) {
		
		int[] result = new int[left.length + right.length];
		
		for (int i = 0, j = 0, k = 0; i < result.length; i++) {
			if (j > left.length - 1) {
				result[i] = right[k];
				k++;
			}
			else if (k > right.length - 1) {
				result[i] = left[j];
				j++;
			}
			else if (left[j] < right[k]) {
				result[i] = left[j];
				j++;
			} else {
				result[i] = right[k];
				k++;
			}
		}
		
		return result;
	}
	
	/**
	 * Gets the left portion of an array where the portion is defined as:
	 * floor(arr.length/2).
	 * 
	 * @param arr the parent array, must not be null
	 * @return int[] the left half of an array
	 */
	private int[] left(int[] arr) {
		
		int[] result;
		if (arr.length == 1) {
			result = arr;
		}
		else if (arr.length == 2) {
			result = new int[1];
			result[0] = arr[0];
		}
		else {
			
			int size = arr.length / 2;	
			result = new int[size];
			for (int i = 0; i < size; i++) {
				result[i] = arr[i];
			}
		}
		return result;
		}
	
	/**
	 * Gets the right portion of an array where the portion is defined as:
	 * ceiling(arr.length/2). 
	 * 
	 * @param arr the parent array, must not be null
	 * @return int[] the right half of an array
	 */
	private int[] right(int[] arr) {
		int[] result;
		if (arr.length == 1) {
			result = arr;
		}
		else if (arr.length == 2) {
			result = new int[1];
			result[0] = arr[1];
		}
		else {
			int offset = arr.length % 2 == 0 ? 0 : 1;
			int size = (arr.length / 2) + offset;
			result = new int[size];
			
			int j = 0;
			int i = (arr.length / 2);
			while (i < arr.length) {
				result[j] = arr[i];
				j++;
				i++;
			}
		}
		return result;
	}
}