package com.w.winterVacation.sort;

/**

 * 归并排序

 *

 * @author wspstart

 * @create 2023-01-26 17:05

 */

public class MergeSort {

    // 归并所需要的辅助数组

    private static int[] assist;

    /*

        比较 v 是否小于 w

     */

    private static boolean less(int v, int w) {

        return v <= w;

    }

    /*

    对数组中 arr 的元素进行排序

     */

    public static void sort(int[] arr) {

        // 1、初始化辅助数组 assist;

        assist = new int[arr.length];

        // 2、定义一个 left 变量和 right 变量，分别记录数组中最小的索引和最大的索引

        int left = 0;

        int right = arr.length - 1;

        // 3、调用 sort 重载方法完成数组 arr 中，从索引 left 到索引 right 的元素的排序

        sort(arr, left, right);

    }

    /*

    对数组 arr 中从 left 到 right 中的元素排序

     */

    private static void sort(int[] arr, int left, int right) {

        // 对传入的数据进行安全性校验

        if (right <= left) {

            return;

        }

        // 对数据进行分组

        int mid = left + ((right - left) >> 1);

        // 对每一组数据进行排序

        sort(arr, left, mid);

        sort(arr, mid + 1, right);

        merge(arr, left, right, mid);

    }

    /**

     * 归并，归并的过程中需要对数据进行排序

     *

     * @param arr   排序的原始数组

     * @param left  左边有序序列的初始索引

     * @param right 右边索引

     * @param mid   中间索引

     */

    private static void merge(int[] arr, int left, int right, int mid) {

        // 定义三个指针

        int i = left; // 表示 assist 数组中已有的有效数据的索引

        int p1 = left; // 左子组的第一个位置

        int p2 = mid + 1; // 右子组的第一个位置

        // 遍历，移动 p1 指针和 p2 指针，比较对应的索引处的值，找出小的那个，放到辅助数组的对应索引处

        while (p1 <= mid && p2 <= right) {

            // 比较对应索引处的值

            if (less(arr[p1], arr[p2])) {

                assist[i++] = arr[p1++];

            } else {

                assist[i++] = arr[p2++];

            }

        }

        // 出了第一个循环之后，两个子组中的某一个子组中的元素已经遍历完成了。

        // 遍历，如果 p2 的指针没有走完，那么顺序移动 p2 指针，把对应的元素放到辅助数组的对应索引处 (下面两个循环只会走一个)

        while (p1 <= mid) {

            assist[i++] = arr[p1++];

        }

        while (p2 <= right) {

            assist[i++] = arr[p2++];

        }

        // 把辅助数组中的元素拷贝到原数组中

        for (int index = left; index <= right; index++) {

            arr[index] = assist[index];

        }

    }

}