1
$\begingroup$

What is the space complexity of Bottom-up merge sort? It uses iteration rather than recursion so it will not use stack. But will an auxiliary array be used for the merge operation? Please explain. Thank you.

$\endgroup$
1
$\begingroup$

Yes, an auxiliary array is required for the merge operation. The space complexity would be $\Theta(n)$, where $n$ is the size of the input.

The merge subroutine can create a temporary array to store the result of the merge operation and its contents can then be copied into the input array. Or, an array having the same size as input can be created in the beginning and passed as an extra argument to the merge subroutine.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.