Creating a temp array vs passing one in Mergesort

Question

In my CS class, we've discussed two ways of dealing with the temporary array required for the merging phase of mergesort. One of them is to pass a full-size temporary array as a parameter, e.g. merge(array, tempArray, first, last), and another is to create a temporary array of appropriate size (or two half-sized arrays) in the function call, e.g.

merge(array, first, last):

...
leftArray = items from first to middle
rightArray = items from middle+1 to last
...

My CS professor is of the opinion that the first option will somehow have a performance (speed/memory) improvement over the second, but I don't understand why. Merging the arrays is a "tail" operation in mergesort, and so the second option doesn't seem like it will actually require more memory overall. Is the only reason why because memory allocation takes time?

Thanks!

Answer 1

Most programming languages pass arrays as function arguments by reference: that is, the function is told where in memory the array is located, rather than being given all the elements directly. This means that, when you call something like

sort (int array A, int left, int right)

only three words of data are passed to the function, regardless of how big the array is – the address of A and the integer values describing the portion of the array to be sorted.

In contrast, the approach of creating two new arrays for the two halves requires allocating memory for the new arrays and copying the data across. Each of these takes a number of operations that is proportional to the size of the array. This is much less efficient, especially when you consider that the algorithm is recursive and will copy the array multiple times.

Answer 2

Memory management would be the only reason. In the second approach, you need to create $2n$ arrays total size of about $2n\log{n}$. If it is happening with a large $n$ or very small computing unit, you will face serious performance issues. Finally, you have to be careful with memory when you work with recursive functions. It easily cause memory overflow.