2-归并排序

算法思想

1. 递归划分区域
2. 归并左右两半区域

记忆口诀

1. 持续划分，直至孤独
2. 临时数组，用于存储

算法模板

public static void mergeSort(int[] q, int l, int r) {  
    if (l >= r) return;  
  
    // 划分区间  
    int mid = l + r >> 1;  
    int i = l, j = mid + 1;  
  
    // 递归处理划分后的两个区间  
    mergeSort(q, l, mid);  
    mergeSort(q, mid + 1, r);  
  
    int k = 0;  
    int[] arr = new int[r - l + 1];  
  
    // 归并两个有序区间  
    while (i <= mid && j <= r) {  
        if (q[i] <= q[j]) arr[k++] = q[i++];  
        else arr[k++] = q[j++];  
    }  
  
    while (i <= mid) {  
        arr[k++] = q[i++];  
    }  
    while (j <= r) {  
        arr[k++] = q[j++];  
    }  
  
    for (i = l, k = 0; i <= r; i++, k++) {  
        q[i] = arr[k];  
    }  
}