这部分代码会在归并排序中执行吗？

Question

合并排序的算法是

Step 1 − if it is only one element in the list it is already sorted, return. Step 2 − divide the list recursively into two halves until it can no more be divided. Step 3 − merge the smaller lists into new list in sorted order.

使用这个伪代码：

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array

   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while

   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while

   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while

   return c

end procedure

我的问题是：

在merge函数中，有两个while循环来检查a和b是否还有项目并将它们添加到c数组。

我的问题是这两个 while 会（可以）在同一个函数中执行吗？

或者如果 a 仍然有项目，这意味着 b 肯定是空的，反之亦然？

Answer 1

没有。如果它们都不为空，那么第一个 while 条件就为真。

第一个while结束后，a,b中至少有一个为空

这部分代码会在归并排序中执行吗？

will this part of the code be executed in the merge sort?

java

algorithm

sorting

merge

mergesort