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

Question

在合并算法中，为什么比较的次数最多是N，至少是N/2。我认为这种比较最多是N/2，因为最多只会有较少的调用(生长素，auxi)。或者，这是否意味着比较包括if(i > mid)和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元素列表的N1，因为如果您在一个值较大的列表和另一个具有较大值的列表之间来回切换，将在输出的每个元素中进行一个比较(最后一个除外)。进行N/2比较的情况实际上是最好的情况；只有当一个列表中的所有元素都严格小于另一个列表中的所有元素时，才会发生这种情况。