In-place sorting with fewer moves
It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n/log log n) element moves, and a log(2)n + O(n log log n) comparisons. This is the first in-place sorting algorithm requiring o(n log n) moves in the worst case while guaranteeing O(n log n) comparisons, but due to the constant factors involved the algorithm is predominantly of theoretical interest. (C) 1999 Elsevier Science B.V. All rights reserved.
sorting in-place algorithms merging mergesort multiway merge