Search code examples
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:

  • bubble sort satisfies 2 and 3
  • merge sort satisfies 1 and 2
  • heap sort satisfies 1 and 3

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