Implementing a mergesort without using an additional array?

Question

I've read a lot about mergesort recently and I wonder if there is a way to do a mergesort without using at least one additional array. Is it possible?

Answer 1

No, you'll always need an extra data structure to merge the sorted elements to. If not you'll just be overwriting the stuff you already sorted.

Answer 2

Apparently, it is. This paper describes an in-place merge sort.

Answer 3

According to Wikipedia it is indeed possible, but might not yield any performance gain:

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. In these cases, algorithms like heapsort usually offer comparable speed, and are far less complex. Additionally, unlike the standard merge sort, in-place merge sort is not a stable sort. In the case of linked lists the algorithm does not use more space than that the already used by the list representation, but the O(log(k)) used for the recursion trace. Some would argue that sorting a linked list is not in place because even though you are sorting in the given data structure, the data structure inherently has O(n) extra data you are manipulating (e.g., the links in the list).

Answer 4

I once have developed one for linked lists in Delphi:

http://www.continuit.nl/index.php?LANGUAGE=EN&PAGE=DOCUMENTS_SORTING