package chap02;

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.Random;

import org.junit.Test;

/***
 * 在归并排序中对小数组采用插入排序
 * 
 * @author xiaojintao
 * 
 */

public class ques2_1 {

    /**
     * 归并排序算法
     * 
     * @param a
     * @return
     */
    static void mergeSortWithInsertSort(int[] a, int start, int end, int k) {
        if (start < end - k) {

            if (start < end - 1) {
                insertSort(a, start, end);
                System.out.println("diaoyongle");
            }
            int mid = (start + end) / 2;
            mergeSortWithInsertSort(a, start, mid, k);
            mergeSortWithInsertSort(a, mid, end, k);
            merge(a, start, mid, end);
        }
    }

    /**
     * 归并排序中将两个已经排序的序列合并
     * 
     * @param a
     * @param b
     * @return
     */
    protected static void merge(int[] n, int start, int mid, int end) {
        int[] l = Arrays.copyOfRange(n, start, mid);
        int[] r = Arrays.copyOfRange(n, mid, end);
        int i = 0;
        int j = 0;// j<mid-start
        int k = 0;// k<end-mid
        while (i < end - start) {
            if (j < mid - start & k < end - mid) {
                if (l[j] < r[k]) {
                    n[i + start] = l[j];
                    j++;
                } else {
                    n[i + start] = r[k];
                    k++;
                }
            } else if (k < end - mid) {
                n[i + start] = r[k];
                k++;
            } else if (j < mid - start) {
                n[i + start] = l[j];
                j++;
            }
            i++;
        }
        // System.out.println(Arrays.toString(n));
    }

    /**
     * 插入排序算法,对序列中从start到end（不包含end）之间的序列插入排序 start<end
     * 
     * @param n
     * @return
     */
    static void insertSort(int[] n, int start, int end) {
        for (int j = start + 1; j < end; j++) {
            int k = n[j];
            int i = j - 1;
            while (n[i] > k) {
                n[i + 1] = n[i];
                i--;
                if (i == start - 1)
                    break;
            }
            n[i + 1] = k;
        }
    }

}