官术网_书友最值得收藏!

Merges and mergesort

As long as we're on the topic of sorting algorithms, let's write sort a different way!

std::inplace_merge(a,mid,b) takes a single range [a,b) which has already been sorted with the equivalent of std::sort(a,mid) and std::sort(mid,b), and merges the two subranges together into a single sorted range. We can use this building block to implement the classic mergesort algorithm:

    template<class RandomIt>
void sort(RandomIt a, RandomIt b)
{
auto n = std::distance(a, b);
if (n >= 2) {
auto mid = a + n/2;
std::sort(a, mid);
std::sort(mid, b);
std::inplace_merge(a, mid, b);
}
}

However, beware! The name inplace_merge seems to imply that the merging is happening "in-place" without the need for any additional buffer space; but this is not what happens in fact. In actuality, the inplace_merge function allocates a buffer for its own use, typically by calling operator new. If you are programming in an environment where heap allocation is problematic, then you should avoid inplace_merge like the plague.

The other standard algorithms that may allocate temporary buffers on the heap are std::stable_sort and std::stable_partition.

std::merge(a,b,c,d,o) is the non-allocating merge algorithm; it takes two iterator-pairs representing the ranges [a,b) and [c,d) and merges them into the output range defined by o.

主站蜘蛛池模板: 通州市| 汝南县| 友谊县| 内黄县| 乌鲁木齐市| 武宣县| 武陟县| 陆川县| 苏尼特右旗| 临江市| 吴旗县| 大城县| 建始县| 清苑县| 洛隆县| 同心县| 百色市| 营山县| 乡宁县| 绥江县| 清水县| 广宗县| 济阳县| 乌兰浩特市| 辉县市| 铁岭县| 栾城县| 武功县| 沛县| 凤阳县| 宜春市| 青浦区| 兴隆县| 庐江县| 金塔县| 名山县| 石嘴山市| 乐清市| 盘山县| 英吉沙县| 青河县|