归并排序 - 非递归实现

import java.util.Arrays;

/**
 * @title MergeSortByNonRecursion
 * @description 归并排序，非递归实现
 * author zzw
 * version 1.0.0
 * create 2024/10/23 22:17
 **/
public class MergeSortByNonRecursion {

    public static void main(String[] args) {
        int[] nums = {5, 1, 1, 2, 0, 0};
        new MergeSortByNonRecursion().sortArray(nums);
        System.out.println(Arrays.toString(nums));
    }

    public int[] sortArray(int[] nums) {
        sort(nums);
        return nums;
    }

    /**
     * 归并排序，非递归处理<br/>
     * <ol>
     *     <li>每次将相邻的两个有序数组进行合并</li>
     *     <li>先从只有一个节点的数组开始（一个节点默认有序，无需做其他处理），从做向右合并</li>
     *     <li>将数组处理完一遍后，将节点个数增大一倍，将合并好的子数组再进行合并</li>
     * </ol>
     *
     * @param arr 排序数组
     */
    public static void sort(int[] arr) {
        // 每次用来合并的子数组中的元素个数，每次增加一倍
        for (int i = 1; i < arr.length; i <<= 1) {
            // 默认左侧数据的起始节点从0开始
            int leftIndex = 0;
            // 计算出中间节点
            int mid = leftIndex + i - 1;
            // 只有中间节点小于数组长度减一的时候，才能保证左右两侧数组都存在数据，这样才需要进行数组的合并
            while (mid < arr.length - 1) {
                // 计算出右侧子数组的最后一个节点下标
                // 该下标取中间节点加子数组长度个数 和 总数组长度的最小值，避免数组越界
                int right = Math.min((mid + i), arr.length - 1);
                // 进行数组合并
                merge(arr, leftIndex, mid, right);
                // 计算下一组需要合并的子数组的左侧数组起始位置
                leftIndex = right + 1;
                // 计算下一组需要合并的子数组的左侧数组终止位置
                // 这里计算用于判断是否还有数据数据放入右侧数组进行合并
                mid = leftIndex + i - 1;
            }
        }
    }


    /**
     * 合并两个有序数组
     *
     * @param arr   两个有序数组所在的有序数据
     * @param left  左侧有序数据在arr数组中的起始位置
     * @param mid   左侧有序数组在arr数组中的终点位置
     * @param right 右侧有序数组在arr数组中的终点位置，起始位置在mid+1处
     */
    public static void merge(int[] arr, int left, int mid, int right) {
        // 使用一个临时数据存放合并后的数据
        int[] tmp = new int[right - left + 1];
        // 临时数据数据合并到的下标
        int i = 0;
        // 左侧有序数据处理到的位置
        int lIndex = left;
        // 右侧有序数据处理到的位置
        int rIndex = mid + 1;

        // 比较左、右两侧的有序数组，谁的值小，将谁放到临时数组中，
        // 然后将临时数组、取值的哪个数组的处理下标向后移动
        // 直到左、右两侧的数组有一个处理完，停止此次处理
        while (lIndex <= mid && rIndex <= right) {
            tmp[i++] = arr[lIndex] <= arr[rIndex] ? arr[lIndex++] : arr[rIndex++];
        }

        // 如果左侧的有序数组没有处理完，将左侧数组的剩余数据放入临时数组中
        while (lIndex <= mid) {
            tmp[i++] = arr[lIndex++];
        }

        // 如果右侧的有序数组没有处理完，将右侧数组的剩余数据放入临时数组中
        while (rIndex <= right) {
            tmp[i++] = arr[rIndex++];
        }

        // 将临时数组中的数据放回原来的数据中
        for (int j = 0; j < i; j++) {
            arr[j + left] = tmp[j];
        }
    }

}