开放原子开发者工作坊

1、  inplace_merge()函数将两个连接在一起的排序序列[first, middle)和[middle, last)结合成单一序列并保持有序。inplace_merge()函数是stable操作。

2、  inplace_merge()版本一的源代码，只讨论了有暂时缓冲区的情况

template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
	BidirectionalIterator middle,
	BidirectionalIterator last) {
	//其中一个序列为空，什么也不做
	if (first == middle || middle == last) return;
	__inplace_merge_aux(first, middle, last, value_type(first),
		distance_type(first));
}
//辅助函数
template <class BidirectionalIterator, class T, class Distance>
inline void __inplace_merge_aux(BidirectionalIterator first,
	BidirectionalIterator middle,
	BidirectionalIterator last, T*, Distance*) {
	Distance len1 = 0;
	distance(first, middle, len1);
	Distance len2 = 0;
	distance(middle, last, len2);
	//会使用额外的内存空间
	temporary_buffer<BidirectionalIterator, T> buf(first, last);
	if (buf.begin() == 0)//内存配置失败
		__merge_without_buffer(first, middle, last, len1, len2);
	else//在有暂时缓冲区的情况下进行
		__merge_adaptive(first, middle, last, len1, len2,
		buf.begin(), Distance(buf.size()));
}
//辅助函数，在有暂时缓冲区的情况下
template <class BidirectionalIterator, class Distance, class Pointer>
void __merge_adaptive(BidirectionalIterator first,
	BidirectionalIterator middle,
	BidirectionalIterator last, Distance len1, Distance len2,
	Pointer buffer, Distance buffer_size) {
	if (len1 <= len2 && len1 <= buffer_size) {
		//case1:缓冲区足够安置序列一
		Pointer end_buffer = copy(first, middle, buffer);
		merge(buffer, end_buffer, middle, last, first);
	}
	else if (len2 <= buffer_size) {
		//case2:缓冲区足够安置序列二
		Pointer end_buffer = copy(middle, last, buffer);
		__merge_backward(first, middle, buffer, end_buffer, last);
	}
	else {//case3:缓冲区不能安置任何一个序列
		BidirectionalIterator first_cut = first;
		BidirectionalIterator second_cut = middle;
		Distance len11 = 0;
		Distance len22 = 0;
		if (len1 > len2) {//序列一比序列二长
			len11 = len1 / 2;
			advance(first_cut, len11);
			second_cut = lower_bound(middle, last, *first_cut);
			distance(middle, second_cut, len22);
		}
		else {//序列二比序列一长
			len22 = len2 / 2;
			advance(second_cut, len22);
			first_cut = upper_bound(first, middle, *second_cut);
			distance(first, first_cut, len11);
		}
		//旋转操作
		BidirectionalIterator new_middle =
			__rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
			len22, buffer, buffer_size);
		//对左段递归调用
		__merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
			buffer_size);
		//对右端递归调用
		__merge_adaptive(new_middle, second_cut, last, len1 - len11,
			len2 - len22, buffer, buffer_size);
	}
}
template <class BidirectionalIterator1, class BidirectionalIterator2,
class Distance>
BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first,
BidirectionalIterator1 middle,
BidirectionalIterator1 last,
Distance len1, Distance len2,
BidirectionalIterator2 buffer,
Distance buffer_size) {
<span style="white-space:pre">	</span>BidirectionalIterator2 buffer_end;
<span style="white-space:pre">	</span>if (len1 > len2 && len2 <= buffer_size) {
<span style="white-space:pre">		</span>//缓冲区能安置序列二
<span style="white-space:pre">		</span>buffer_end = copy(middle, last, buffer);
<span style="white-space:pre">		</span>copy_backward(first, middle, last);
<span style="white-space:pre">		</span>return copy(buffer, buffer_end, first);
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>else if (len1 <= buffer_size) {
<span style="white-space:pre">		</span>//缓冲区能安置序列一
<span style="white-space:pre">		</span>buffer_end = copy(first, middle, buffer);
<span style="white-space:pre">		</span>copy(middle, last, first);
<span style="white-space:pre">		</span>return copy_backward(buffer, buffer_end, last);
<span style="white-space:pre">	</span>}
<span style="white-space:pre">	</span>else  {
<span style="white-space:pre">		</span>//缓冲区不足，调用rotate()函数
<span style="white-space:pre">		</span>rotate(first, middle, last);
<span style="white-space:pre">		</span>advance(first, len2);
<span style="white-space:pre">		</span>return first;
<span style="white-space:pre">	</span>}
}

3、  图解说明

case 1:缓冲区足够安置序列一

case 2:缓冲区足够安置序列二

case 3:假设缓冲区大小为3，小于序列一的长度4和序列二的长度5，缓冲区不能安置任何一个序列

 旋转操作后：

左段递归调用：

右端递归调用：

排序完成。