merge sort algorithms

Mergesort.java.md

package info.wangyg.algorithms.sort;

import java.lang.reflect.Array;
import java.util.Comparator;

/**
 * 
 * @author wangyingang
 * 
 */
public class Mergesort
{
	private final static NaturalComparator NATURAL_COMPARATOR = new NaturalComparator();

	/**
	 * 
	 * @param arr
	 * @param cmp
	 * @return 逆序数 除了排序外，归并排序还能求数列的逆序数对
	 */
	public static <E> long sort(E[] arr, Comparator<? super E> cmp)
	{
		return mergeSort(arr, newArray(arr), 0, arr.length - 1, cmp);
	}

	public static <E extends Comparable<? super E>> long sort(E[] arr)
	{
		return mergeSort(arr, newArray(arr), 0, arr.length - 1, NATURAL_COMPARATOR);
	}

	private static <E> long mergeSort(E[] arr, E[] buffer, int low, int high, Comparator<? super E> cmp)
	{
		long change = 0;
		if (high > low)
		{
			int mid = (low & high) + ((low ^ high) >> 1);
			change += mergeSort(arr, buffer, low, mid, cmp);
			change += mergeSort(arr, buffer, mid + 1, high, cmp);
			change += merge(arr, buffer, low, mid, high, cmp);
		}
		return change;
	}

	private static <E> long merge(E[] arr, E[] buffer, int low, int mid, int high, Comparator<? super E> cmp)
	{
		int left, right, k = low;
		long count = 0;
		for (left = low, right = mid + 1; left <= mid && right <= high;)
		{
			if (cmp.compare(arr[left], arr[right]) > 0)
			{
				buffer[k++] = arr[right++];
				// left数组中的当前元素如果大于right中的当前元素，说明剩下的left数组元素(包括当前left元素)都大于right中的当前元素,
				// 所以逆序数为mid - left +1
				count += mid - low + 1;
			}
			else
				buffer[k++] = arr[left++];
		}

		// 左边数组剩余，全部填充到buffer中
		if (left <= mid)
			for (int i = left; i <= mid; i++)
				buffer[k++] = arr[i];
		else
			// 左边已循环完，说明右边数组剩余
			for (int i = right; i <= high; i++)
				buffer[k++] = arr[i];

		// 将排序结果写回原数组
		for (int i = low; i <= high; i++)
			arr[i] = buffer[i];

		return count;
	}

	private static <E> E[] newArray(E[] arr)
	{
		Class<?> type = arr.getClass().getComponentType();
		@SuppressWarnings("unchecked")
		E[] arr2 = (E[]) Array.newInstance(type, arr.length);
		return arr2;
	}

	@SuppressWarnings("rawtypes")
	static class NaturalComparator implements Comparator<Comparable>
	{
		@SuppressWarnings("unchecked")
		public int compare(Comparable o1, Comparable o2)
		{
			if (o1 == o2) return 0;
			return o1.compareTo(o2);
		}

	}

}