在浏览维基百科的排序算法列表时,我注意到没有一种稳定的比较排序具有O(n*log(n))
(最坏情况)时间复杂性和O(1)
(最坏条件)空间复杂性。这看起来确实是一个理论边界,但我找不到更多关于它的信息
如何证明这一点
注意:我知道比较排序的O(n*log(n))
最坏情况时间复杂度的下限。
不管那篇文章怎么说,就地稳定的Merge Sort可以变成O(n log n)
。
这篇论文解释了实现它的两种方法。
这里是一个完整的C++实现,我从这里的C实现转换而来:
#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);
}