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

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

Two in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log 2 N + O(N ) comparisons and 3N log 2 N + O(N ) moves to sort N elements. The second, more advanced variant requires at most N log 2 N + O(N ) comparisons and "N log 2 N moves, for any fixed " ? 0 and any N ? N ("). In theory, the second one is superior to advanced versions of heapsort. In practice, due to the overhead in the index manipulation, our fastest in-place mergesort behaves still about 50 per cent slower than the bottom-up heapsort. However, our implementations are practical compared to mergesort algorithms based on in-place merging.

Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola, "Practical In-Place Mergesort" (1996).

Answer 2

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).