The running time of MergeSort $($described below$)$ on any input of length $n$ is

$(nlogn)$

$.$ You may assume that the running time of Merge$(A,B)$ is $|A|+|B|.$

MergeSort$($L$)\{$

if list $L$ has one element

return $0$ and the list $L$

Divide the list into two $($equal$)$ halves A and $B$

$A=$ MergeSort$($A$)$

$B=$ MergeSort $(B)$

$L=$Merge$(A,B)$

return $L$

$\}$

True

False