package learn.note.algorithm.sort.three;

import java.util.Arrays;

/**
 * @author Wang WenLei
 * @date 2025/7/30 17:29
 * @since 1.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int [] data = {5,4,3,2,1};
        mergeSort(data);
        Arrays.stream(data).forEach(System.out::print);

        // 对数器
        CompareMachineUtil.compare(MergeSort::mergeSort, null);
    }

    public static void mergeSort(int [] data) {
        mergeSort(data,0,data.length-1);
    }

    public static void mergeSort(int [] data,int low,int high){
        if (data == null || high - low < 1) {
            return;
        }
        int middle = low + ((high - low) >> 1);
        mergeSort(data,low,middle);
        mergeSort(data,middle + 1, high);
        // 合并
        merge(data,low,middle,high);
    }

    private static void merge(int[] data, int low, int middle, int high) {
        int[] tempArr = new int[high - low + 1];
        int i = 0;
        int p1 = low;
        int p2 = middle + 1;

        // 这里都需要等于，左边是从0开始到分界点。右边是从分界点+1开始到数组结束
        // 边界都是闭区间，所以需要等于
        while (p1 <= middle && p2 <= high) {
            if (data[p1] < data[p2]) {
                tempArr[i++] = data[p1++];
            } else {
                tempArr[i++] = data[p2++];
            }
        }
        while (p1 <= middle) {
            tempArr[i++] = data[p1++];
        }
        while (p2 <= high) {
            tempArr[i++] = data[p2++];
        }

        for (i = 0 ; i < tempArr.length ; i++) {
            data[low + i] = tempArr[i];
        }
    }
}