package algorithm.sort.compare.merge;

import java.util.Arrays;
 
 
public class MergeSort { 
    
    public static void main(String[] args) {
        int[] arrayA = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };
        mergeSort (arrayA, 0, arrayA.length - 1, new int[arrayA.length]);
        System.out.println (Arrays.toString (arrayA));
    }
 
        
 
        
    private static void mergeSort ( int[] array, int start, int end, int[] tempArray ){
        if (end <= start)      
            return;      
        int middle = ( start + end )/2;
        mergeSort (array, start, middle, tempArray);
        mergeSort (array, middle + 1, end, tempArray);
        
        int k = 0, leftIndex = 0, rightIndex = end - start;
        System.arraycopy (array, start, tempArray, 0, middle - start + 1);
        for ( int i = 0; i < end - middle; i++ )      
            tempArray[end - start - i] = array[middle + i + 1];      
        while (k < end - start + 1){
            if (tempArray[rightIndex] > tempArray[leftIndex]) // 从小到大          
                array[k + start] = tempArray[leftIndex++];          
            else           
                array[k + start] = tempArray[rightIndex--];           
            k++;
        }
    }
 
   
   
   
}