Merge Sort: Are the additional array copies necessary?

In "Introduction to Algorithms" the merge sort algorithm is implemented with a helper function called MERGE(A, p, q, r) - that is merging two previously sorted sequences .

This function introduces two additional arrays L and R .

MERGE(A, p, q, r)
1 n1 ← q − p + 1
2 n2 ←r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
.....

By "create arra开发者_开发知识库ys L[1 . . n1 + 1] and R[1 . . n2 + 1]" I understand to allocate additional memory for both of them .

Is it possible to re-write this function, so that I won't need the additional memory, and to operate directly to A ?

Sure. It is called in-place merge sort.

Wikipedia say it is complicated -- but it is not always true. Some are not as complicated as others, if you don't care about the run-time.

There are a few variance, some are stable, some are non-stable. See the "implementation" section under NIST DIAGS for some example.

Yes, it's called in-place merge sort, but as Wikipedia puts it:

Sorting in-place is possible (e.g., using lists rather than arrays) but is very complicated, and will offer little performance gains in practice, even if the algorithm runs in O(n log n) time. (Katajainen, Pasanen & Teuhola 1996)

That is possible. http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps