许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法一次或多次递归调用其自身以解决紧密相关的若干子问题。

分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后在合并这些子问题的解来建立原问题的求解。

分治模式在每层递归时都有三个步骤：

1. 分解：分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。

2. 解决：解决这些子问题，递归的求解子问题。若子问题的规模足够小，则直接求解。

3. 合并：合并这些子问题的解成原问题的解。

归并排序算法完全遵循分治模式：

1. 分解：分解待排序的n个元素的序列成各具有n/2个元素的两个子序列。

2. 解决：使用归并排序递归的排序两个子序列。

3. 合并：合并两个已经排序的子序列为最终的排序结果。

完成合并的过程MERAGE(A,p,q,r)，其中A是一个数组，p,q,r是数组下标，满足p<=q<r。该过程假设子数组A[p...q] 和 A[q+1...r]都已经排好序，他合并这两个子数组成单一的已经排好序的子数组并代替当前的子数组A[p...r]。

归并排序的时间复杂度

归并排序的Java实现

package sort;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * User: ASUS
 * Date: 14-9-21
 * Time: 下午3:28
 * To change this template use File | Settings | File Templates.
 */
public class MergeSort {

    private double[] bridge; //辅助数组


    /**
     * 排序
     *
     * @param obj
     */
    public void sort(double[] obj) {
        if (obj == null) {
            throw new NullPointerException("the param can not be null");
        }
        bridge = new double[obj.length]; //初始化中间数组
        mergeSort(obj, 0, obj.length - 1);
        bridge = null;
    }

    /**
     * 归并排序
     * @param obj
     * @param left
     * @param right
     */
    private void mergeSort(double[] obj, int left, int right) {

        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(obj, left, center);
            mergeSort(obj, center + 1, right);
            merge(obj, left, center, right);
        }
    }

    private void merge(double[] obj, int left, int center, int right) {
        int mid = center + 1;
        int third = left;
        int tmp = left;
        while (left <= center && mid <= right) {
            if (obj[left] - obj[mid] <= 10E-6) {
                bridge[third++] = obj[left++];
            } else {
                bridge[third++] = obj[mid++];
            }
        }

        while (mid <= right) {
            bridge[third++] = obj[mid++];
        }

        while (left <= center) {
            bridge[third++] = obj[left++];
        }

        copy(obj, tmp, right);
    }

    private void copy(double[] obj, int left, int right) {
        while (left <= right) {
            obj[left] = bridge[left];
            left++;
        }
    }


    public static void main(String args[]) {

        Random random = new Random(6);
        int arraysize = 10;
        double[] sorted = new double[arraysize];
        System.out.println("before sort");


        // 使用随机数构建一个数组
        for (int j = 0; j < arraysize; j++) {
            sorted[j] = (int) (random.nextDouble() * 100);
            System.out.println((int) sorted[j] + "");
        }

        System.out.println();

        MergeSort sorter = new MergeSort();
        sorter.sort(sorted);
        System.out.println("after sort");

        for (int j = 0; j < sorted.length; j++) {
            System.out.println((int) sorted[j] + "");
        }

        System.out.println();
    }
}

====END====