import java.util.Arrays;

/**
 * 归并排序
 *
 * @author Alfred.Ning
 * @since 2024年08月18日 20:24:00
 */
public class MergeSort {

  public static void main(String[] args) {
    int[] nums = {8, 4, 5, 7, 9, 3, 2, 6, 1};
    int[] nums1 = new int[nums.length];
    System.arraycopy(nums, 0, nums1, 0, nums.length);
    MergeSort mergeSort = new MergeSort();
    mergeSort.mergeSort(nums);
    mergeSort.sort(nums1);
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] != nums1[i]) {
        System.out.println("!!!false");
      }
    }
    System.out.println("!!!pass");
  }

  public void mergeSort(int[] nums) {
    if (nums == null || nums.length == 0) {
      return;
    }

    // 中间数组 用来存储merge 中间结果
    int[] tmp = new int[nums.length];
    mergeSort(nums, 0, nums.length - 1, tmp);
  }

  private void mergeSort(int[] nums, int start, int end, int[] tmp) {
    if (start >= end) {
      return;
    }
    int middle = (start + end) / 2;
    mergeSort(nums, start, middle, tmp);
    mergeSort(nums, middle + 1, end, tmp);
    merge(nums, start, end, tmp);
  }

  private void merge(int[] nums, int start, int end, int[] tmp) {
    int middle = (start + end) / 2;
    int leftIndex = start;
    int rightIndex = middle + 1;
    int index = leftIndex;
    while (leftIndex <= middle && rightIndex <= end) {
      if (nums[leftIndex] < nums[rightIndex]) {
        tmp[index++] = nums[leftIndex++];
      } else {
        tmp[index++] = nums[rightIndex++];
      }
    }
    while (leftIndex <= middle) {
      tmp[index++] = nums[leftIndex++];
    }
    while (rightIndex <= end) {
      tmp[index++] = nums[rightIndex++];
    }

    for (int i = start; i <= end; i++) {
      nums[i] = tmp[i];
    }
  }

  // 对数
  public void sort(int[] nums) {
    Arrays.sort(nums);
  }

}