乍一看,合并排序的空间复杂度为O( n )是有意义的,因为要对未排序的数组进行排序,我将拆分并创建子数组,但所有子数组的大小之和将为n。
问题:我主要关心的是递归过程中mergerSort()函数的记忆分配。我有一个主堆栈,对mergerSort()的每个函数调用(通常)都会被推到堆栈上。现在,每个被反复调用的mergeSort()函数都将有自己的堆栈。因此,假设我们对mergeSort()进行了5个反向调用,那么主堆栈将包含5个函数调用,其中每个函数调用都有自己的函数堆栈。现在,每个函数堆栈都有自己的本地变量,比如函数创建的左子数组和右子数组。因此,在记忆中,5个函数堆栈中的每个都应该有5