sortingstable-sort

Is it possible to stably sort an array in O(n log n) with constant auxilliary space?


Given an array of n elements, is there a sorting algorithm that

  1. sorts in at most O(n log n) time (and optionally, O(n) time in the best case)
  2. is stable
  3. takes O(1) auxilliary space

All sorting algorithms I found satisfy only two of these criteria:

Is there an algorithm that satisfies all three criteria?


Solution

  • From: https://cstheory.stackexchange.com/

    There exists a stable in-place sorting algorithm with O(n log n) comparisons and O(n) moves.

    See: Gianni Franceschini: Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves. Theory Comput. Syst. 40(4): 327-353 (2007) Link