package sort;

import sort.swap.QuickSort;

import java.util.Arrays;

/**
 * @author chenyi
 * @Description 歸并排序
 * @date 2022/2/15 14:07
 */
public class MergeSort {

    public void solution(int[] arr, int start, int end){
        if(start>=end){
            return;
        }
        int m = (end+start)>>1;
        solution(arr,start,m);
        solution(arr,m+1,end);
        // 合并,合并的結(jié)果存于臨時(shí)數(shù)組
        int[] arr2 = new int[end-start+1];
        int i=start,j=m+1,k=0;
        while (i<=m&&j<=end) {
            if(arr[i]<arr[j]) {
                arr2[k++] = arr[i];
                i++;
            }else {
                arr2[k++] = arr[j];
                j++;
            }
        }
        while (i<=m) {
            arr2[k++] = arr[i];
            i++;
        }
        while (j<=end) {
            arr2[k++] = arr[j];
            j++;
        }
        // 將合并的結(jié)果拷貝到原數(shù)組中
        for (int l = 0; l < k; l++) {
            arr[l+start] = arr2[l];
        }
        System.out.println(Arrays.toString(arr2));
    }

    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        new MergeSort().solution(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}