Merge Sort: Are the additional array copies necessary?

Question

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 arrays 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 ?

score 2 · Accepted Answer · edited May 23 '17 at 12:11

2

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.

edited May 23 '17 at 12:11

Community

1
1

answered Nov 29 '10 at 14:48

J-16 SDiZ

26,473
4
65
84

see also this question: http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm – J-16 SDiZ Nov 29 '10 at 14:59

score 1 · Answer 2 · answered Nov 29 '10 at 14:49

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)

score 1 · Answer 3 · answered Nov 29 '10 at 14:53

1

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

answered Nov 29 '10 at 14:53

rik

8,592
1
26
21

Merge Sort: Are the additional array copies necessary?

3 Answers3