Javaでのマージソート

Leetcodeというサイトで912. Sort an Arrayという問題を解いています。
912. Sort an Array

Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

これに対する一つの回答例として、配列を細かく分割してから、マージする以下のやり方が記載されていましたが、
mergeのメソッドの部分が理解できないので、以下の質問をさせてください。

１： int[] tmp = new int[r - l + 1];
の部分についてr - l + 1はこれまでの配列の要素と新しい要素比較する要素を比べるために+ 1としているのでしょうか？

２：int i = l, j = mid + 1, k = 0;
ですがj = mid + 1で＋１するのは何故なのでしょうか、
分割前の配列を２つに分ける場合、lからmidまでが一つの配列、配列を分割した地点+1（mid + 1からr）がもう一つの配列、という理解で良いのでしょうか？

３：while (i <= mid || j <= r)とするのはなぜなのでしょうか。ループする際に、分割された各々の配列の長さを超えないため、という理解で良いのでしょうか。

４：if (i > mid || j <= r && nums[i] > nums[j])について
nums[i] > nums[j]については要素の比較なのでわかるのですが、i > midの存在意義がいまいちピンときていません。

java
1class Solution {
2    public int[] sortArray(int[] nums) {
3        int[] res = new int[nums.length];
4        if (nums == null || nums.length == 0) return res;
5        mergeSort(nums, 0, nums.length - 1);
6        return nums;
7    }
8    private void mergeSort(int[] nums, int l, int r) {
9        if (l >= r) return;
10        int mid = l + (r - l) / 2;
11        mergeSort(nums, l, mid);
12        mergeSort(nums, mid + 1, r);
13        merge(nums, l, r);
14    }
15    private void merge(int[] nums, int l, int r) {
16        int mid = l + (r - l) / 2;
17        int[] tmp = new int[r - l + 1];
18        int i = l, j = mid + 1, k = 0;
19        while (i <= mid || j <= r) {
20            if (i > mid || j <= r && nums[i] > nums[j]) {
21                tmp[k++] = nums[j++];
22            } else {
23                tmp[k++] = nums[i++];
24            }
25        }
26        System.arraycopy(tmp, 0, nums, l, r - l + 1);
27    }
28}

行動規範の内容に同意します

回答1件

ベストアンサー

１： int[] tmp = new int[r - l + 1];

の部分についてr - l + 1はこれまでの配列の要素と新しい要素比較する要素を比べるために+ 1としているのでしょうか？

r - l + 1 は、配列 num の中のソート対象としている l から r までの要素の個数です。

２：int i = l, j = mid + 1, k = 0;

ですがj = mid + 1で＋１するのは何故なのでしょうか、
分割前の配列を２つに分ける場合、lからmidまでが一つの配列、配列を分割した地点+1（mid + 1からr）がもう一つの配列、という理解で良いのでしょうか？

その理解でよろしい。

３：while (i <= mid || j <= r)とするのはなぜなのでしょうか。ループする際に、分割された各々の配列の長さを超えないため、という理解で良いのでしょうか。

その理解でよろしい。

４：if (i > mid || j <= r && nums[i] > nums[j])について

nums[i] > nums[j]については要素の比較なのでわかるのですが、i > midの存在意義がいまいちピンときていません。

i > mid の場合、l から mid までの配列要素は全部 tmp に入れてしまったということです。
したがって、nums[i] > nums[j] の比較をせずに tmp に nums[j] を入れてよいということです。

追記
tmp を何度も new するのは無駄だし、
merge の wihleループで、i <= mid、j <= r、i > mid、j <= r の
比較を行うのも効率が悪いので書き直してみました。

Java
1class Solution {
2	int[] tmp;
3
4    public void sortArray(int[] nums) {
5		tmp = new int[nums.length];
6        mergeSort(nums, 0, nums.length - 1);
7    }
8    private void mergeSort(int[] nums, int l, int r) {
9        if (l >= r) return;
10        int mid = l + (r - l) / 2;
11        mergeSort(nums, l, mid);
12        mergeSort(nums, mid + 1, r);
13        merge(nums, l, mid, r);
14    }
15    private void merge(int[] nums, int l, int mid, int r) {
16        System.arraycopy(nums, l, tmp, l, mid - l + 1);
17		for (int i = mid + 1, k = r; i <= r; )
18			tmp[k--] = nums[i++];
19		for (int i = l, j = r, k = l; i <= j; )
20			nums[k++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j--];
21    }
22
23	public static void main(String[] args) {
24		int[] nums = { 5, 1, 1, 2, 0, 0 };
25		Solution sol = new Solution();
26		sol.sortArray(nums);
27		System.out.println(java.util.Arrays.toString(nums));
28	}
29}