Stable comparison of comparison with O (n * log (n)) time and O (1) complexity

Question

Looking through the List of sorting algorithms on Wikipedia, I noticed that there is no stable sorting sorting that has O(n*log(n)) (worst case) time complexity and O(1) (worst case) space complexity. It certainly looks like a theoretical boundary, but I could not find more information about it.

How would I confirm this?

Note. I know about the lower limit O(n*log(n)) worst time complexity for sorting sorts.

Answer 1

Despite what is said in this article, a stable Merge Sort merge can be done O(n log n) .

Here is a document that explains two ways to implement it.

Answer 2

Here is the full C ++ implementation that I converted from the C implementation here :

 #include <algorithm> #include <functional> template<class It> It rotate(It begin, It const middle, It end) { typename std::iterator_traits<It>::difference_type i = 0, j; if (begin != middle && middle != end) { while ((i = std::distance(begin, middle)) != (j = std::distance(middle, end))) { It k = middle; std::advance( k, std::max( typename std::iterator_traits<It>::difference_type(), j - i)); std::swap_ranges(k, end, begin); if (i > j) { std::advance(begin, j); } else { std::advance(end, -i); } } } return std::swap_ranges(middle - i, middle, middle); } template<class It, class Less> It bsearch( It begin, It left, It right, typename std::iterator_traits<It>::difference_type n, Less &less) { while (left < right) { It const middle = left + std::distance(left, right) / 2; bool const b = !less( *(begin + (std::distance(middle, begin) + n)), *middle); (b ? left : right) = middle + b; } return left; } template<class It, class Less> void merge(It const begin, It const middle, It const end, Less &less) { bool naive_insertion_optimization = false; if (naive_insertion_optimization && std::distance(begin, end) < 0) { for (It i = middle; i != end; ++i) { for (It p = i; p != begin; --p) { if (!less(*p, *(p - 1))) { break; } using std::iter_swap; iter_swap(p, p - 1); } } } else if (begin < middle && middle < end) { typename std::iterator_traits<It>::difference_type const half = std::distance(begin, end) / 2, left = std::distance(begin, middle), right = std::distance(middle, end); It const midpoint = begin + half; bool const b = left > right; It const i = bsearch( begin, b ? midpoint - right : begin, b ? midpoint : middle, half + left - 1, less); rotate(i, middle, begin + (std::distance(i, middle) + half)); merge(begin, i, midpoint, less); merge(midpoint, midpoint + std::distance(i, middle), end, less); } } template<class It, class Less> void sort(It const begin, It const end, Less &less) { if (std::distance(begin, end) > 1) { It const middle = begin + std::distance(begin, end) / 2; sort(begin, middle, less); sort(middle, end, less); merge(begin, middle, end, less); } } template<class It> void sort(It const begin, It const end) { std::less<typename std::iterator_traits<It>::value_type> less; return sort(begin, end, less); }