将数组的两个已排序的半部分合并为一个已排序的数组。

/**来 自 时 代      J a v a   公   众 号 - nowjava.com**/

//package com.nowjava;

import java.util.ArrayList;


public class Main {

    /**

     * merges two sorted halves of an array into a single sorted array. Assumes that the input array to be sorted 

     *    has fully sorted sub-arrays to the left and right of some particular index

     * 

     * @param arrayList the ArrayList whose sub-arrays you want to merge

     * @param tempArray a working array that will hold the merged array as it is being built from the sub-arrays of ArrayList

     * @param first the starting index of left side's sorted sub-array

     * @param mid the starting index of the right side's sorted sub-array

     * @param last the ending index of the right side's sorted sub-array

     */

    public static <T extends Comparable<? super T>> void merge(

            ArrayList<T> arrayList, T[] tempArray, int first, int mid,

            int last) {

        if (last > first && last >= mid && mid >= first) {

            int tempIndex = first;

            int start1 = first;

            int end1 = mid - 1;

            int start2 = mid;
            /** 
            来 自 
            N o  w  J a v a . c o m - 时  代  Java
            **/

            int end2 = last;

            while ((end1 - start1) > -1 && (end2 - start2) > -1) {

                if (arrayList.get(start1).compareTo(arrayList.get(start2)) <= 0) {

                    tempArray[tempIndex] = arrayList.get(start1);

                    start1++;

                } else {

                    tempArray[tempIndex] = arrayList.get(start2);

                    start2++;

                }

                tempIndex++;

            }

            // assume that one of the sub-arrays has been completely been added to the temporary array by this point

            while ((end1 - start1) > -1) {

                tempArray[tempIndex] = arrayList.get(start1)