[TOC]

algorithm 4th(2.2)归并排序

说明：

• 归并排序需要一个和要排序数组一样容量的的数组
• 归并排序分为自顶向下和自下向上两种方案，自下向上用于链表实现（只需调整指针即可）
• 归并排序中，使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%~15%。

思考：

1. 为什么能缩短时间？
2. 为什么使用插入排序，使用选择排序行吗？（稳定排序的角度想一下）

import java.io.File;
import java.net.URL;
import java.util.Scanner;

/**
 * Created by admin on 2016/11/20.
 */
public class Merge {
    private static Comparable[] aux;

    //一趟归并，前提a[lo,mid]有序 ,a(mid,hi]有序
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        // (lo,mid)(mid,hi)
        int i = lo, j = mid + 1;
        for (int k = lo; k < hi; k++) {
            aux[k] = a[k];
        }
        for (int k = lo; k < hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = a[j++];
            else a[k] = aux[i++];
        }
    }

    //归并排序算法实现(自顶向下)
    public static void mergeSort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        mergeSort(a, 0, N);
    }

    private static void mergeSort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    //归并排序算法实现，自下向上
    private static void mergeSortUP(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        //
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N));
            }
        }
    }
    //
    public static void sort(Comparable[] a) {
        mergeSort(a);
    }

    //判断两个数字的大小 v < w : true
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    //交换两个数
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    //
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    //检查a是否有序，用于对排序后的数据检测
    public static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i - 1])) return false;
        }
        return true;
    }

    private static String[] readDataFromFile(String fileName) throws Exception {
        /*
         *从data.in中读取数据，然后把数据转换成Integer(包装了有Comparable接口)
         */
        URL url = Merge.class.getClassLoader().getResource(fileName);
        File file = new File(url.getPath());
        Scanner sc = new Scanner(file);

        String str = sc.nextLine();
        return str.split(" ");
    }

    public static void main(String[] args) throws Exception {
        //设计成从文件读入数据，然后把数据(maven下，数据放在resources目录)
        String[] ss = readDataFromFile("ch02/data.in");

        int N = ss.length;
        Integer[] arr = new Integer[N];
        for (int i = 0; i < N; i++) {
            arr[i] = new Integer(Integer.parseInt(ss[i]));
        }

        sort(arr);
        //    assert isSorted(arr);
        show(arr);
    }
}