import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

public class SortAlgorithms {
/**
     * 归并排序算法
     * 
     * @param a
     * @return
     */
    static void mergeSort(int[] a, int start, int end) {
        if (start < end - 1) {
            int mid = (start + end) / 2;
            mergeSort(a, start, mid);
            mergeSort(a, mid, end);
            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++;
        }
    }

}