归并排序，,package sort

归并排序，,package sort

package sort;public class MergeSort {    public static void merge(int[] array,int start1st,int start2nd, int end2nd){        /*         * cur1 refers to the first item of a         * cur2 refers to the first item of b         * cur3 refers to the index of the next location of temp         */        int[] temp = new int[array.length];        int cur1 = start1st, cur2 = start2nd, cur3 = start1st;        /*         * if there exists a current item in both sequence         * if array[cur1] <= array[cur2]         * move array[cur1] to the right end of cur3         * else move array[cur2] to the right end of cur3         */        while((cur1 < start2nd)&&(cur2 <= end2nd)){            if(array[cur1] <= array[cur2]){                temp[cur3] = array[cur1];                cur1++;                cur3++;            }else{                temp[cur3] = array[cur2];                cur2++;                cur3++;            }        }        while(cur1 < start2nd){            temp[cur3] = array[cur1];            cur1++;            cur3++;        }        while(cur2 <= end2nd){            temp[cur3] = array[cur2];            cur2++;            cur3++;        }        cur1 = start1st;        cur3 = start1st;        while(cur3 <= end2nd){            array[cur1] = temp[cur3];            cur1++;            cur3++;        }    }     /*     * void MergeSort(int array[], int first, int last)　　   *{    　　  int mid = 0;    　　  if(first<last)    　　   *{    　　   *mid = (first+last)/2;    　　   *MergeSort(array, first, mid);    　　   *MergeSort(array, mid+1,last);    　　   *Merge(array,first,mid,last);　　   *}　　   *}     *      *      *      *      *      *      */    public static void mergeSort(int[] array,int first,int last){        int mid;        if(first < last){            mid = (first + last)/2;            mergeSort(array,first,mid);            mergeSort(array,mid+1,last);            merge(array,first,mid,last);        }    }}//该片段来自于http://byrx.net