如何理解合并算法中进行了多少次比较？

Question

merge算法中，为什么比较次数最多为N次，最少为N/2。我认为比较最多是 N/2，因为最多会调用 less(aux[j], aux[i])。或者这是否意味着比较包括以下陈述 if(i > mid) 和 else if (j > hi )?谢谢！

public static void merge(Comparable[] a, int lo, int mid, int hi) 
{ 
    for (int k = lo; k <= hi; k++) 
        aux[k] = a[k];

    for (int k = lo; k <= hi; k++) 
    if(i > mid)  a[k] = aux[j++];
    else if (j > hi )  a[k] = aux[i++];
    else if (less(aux[j], aux[i])) a[k] = aux[j++]; 
    else  a[k] = aux[i++];
}

Answer 1

例如，假设您想将这些列表合并在一起：

1 3 5 7 9
2 4 6 8 10

本作品工作原理如下：

1 3 5 7 9
2 4 6 8 10
^
+--------------- Compare 1 and 2, output 1

3 5 7 9
2 4 6 8 10
^
+--------------- Compare 3 and 2, output 2

3 5 7 9
4 6 8 10
^
+--------------- Compare 3 and 4, output 3

5 7 9
4 6 8 10
^
+--------------- Compare 5 and 4, output 4

5 7 9
6 8 10
^
+--------------- Compare 5 and 6, output 5

7 9
6 8 10
^
+--------------- Compare 7 and 6, output 6

7 9
8 10
^
+--------------- Compare 7 and 8, output 7

9
8 10
^
+--------------- Compare 9 and 8, output 8

9
10
^
+--------------- Compare 9 and 10, output 9


10
^
+--------------- Output 10

此处共有 10 个元素，如您所见，需要进行 9 次比较。对于 N 元素列表，将进行的最大比较次数实际上是 N - 1，因为如果您在一个具有较大值的列表和另一个具有较大值的列表之间来回交替，将对每个元素进行一次比较输出（除了最后一个）。进行N/2次比较的情况实际上是最好的可能情况；只有当一个列表中的所有元素都严格小于另一个列表中的所有元素时才会发生这种情况。

如何理解合并算法中进行了多少次比较？

How to understand how many comparisons are made in the merge algorithm?

algorithm

merge