package cn.firstflag.crm.service;

import org.apache.log4j.Logger;

/**
 * 
 * @author zhanmin.zheng
 *
 */
public class mergerSortTest {
    
    private static Logger log = Logger.getLogger(mergerSortTest.class);
    
    public void merger() {
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };  
        mergerSort(data, 0, data.length-1);
    }
    
    public static void mergerSort(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }
        
        int center = (left + right) /2;
        mergerSort(data, left, center);
        
        mergerSort(data, center + 1, right);
        
        sort(data, left, center, right);
        
        log.info (data.toString());
        
    } 
    
    /**
     * 归并
     * @param data
     * @param left
     * @param center
     * @param right
     */
    public static void sort(int[] data, int left, int center, int right) {
        int[] tempArr = new int[data.length];
        /** 右数组的第一个元素 */
        int mid = center+1;
        /** 临时数组的索引 */
        int third = left;
        /** 缓存数组第一个元素的索引 */
        int tmp = left;
        
        /**
         *  从两个数组中取出最小的放入临时数组  
         */
        while (left <=center && mid <= right) {
            if (data[left] <= data[mid]) {
                tempArr[third++] = data[left++];
            } else {
                tempArr[third++] = data[mid++];
            }
        }
        
        /**
         * 将剩余数组加入到临时数组的尾端
         */
        while (left <= center) {
            tempArr[third++] = data[left++];    
        }
        
        while (mid <= right) {
            tempArr[third++] = data[mid++];
        }
        
        /**
         * 将临时数组中的内容拷贝回原数组中 
         * 原left-right范围的内容被复制回原数组）  
         */
        while (tmp <= right) {  
            data[tmp] = tempArr[tmp++];  
        }  
    }
}