题解 | JAVA MergeSort (in-place)#排序# [P0]

时间: O(nlogn)
空间: O(n)

import java.util.*;

public class Solution {
  
    public int[] MySort (int[] arr) {
      mergeSort(0, arr.length-1, arr);
      return arr;
    }
  
    // in-place mergeSort
    void mergeSort(int lo, int hi, int[] arr) {
      if (lo >= hi) return;
      
      int mid = lo + ((hi-lo)>>1);
      mergeSort(lo, mid, arr);
      mergeSort(mid+1, hi, arr);
      merge(lo, mid, hi, arr);
    }
  
    // arr[lo, mid] and arr[mid+1, hi] are sorted, 
    void merge(int lo, int mid, int hi, int[] arr) {
      int[] la = Arrays.copyOfRange(arr, lo, mid+1);
      int[] ra = Arrays.copyOfRange(arr, mid+1, hi+1);
      
      int l = 0, r = 0;
      for (int i = lo; i <= hi; i++) {
        if (l < la.length && (r >= ra.length || la[l] <= ra[r])) {
          arr[i] = la[l]; 
          l++;
        } else {
          arr[i] = ra[r];
          r++;
        }
      }
    }
}