原地归并排序的时间复杂度为O(nlog2n)，空间复杂度为O(logn)，相对于传统的非原地归并排序(时间复杂度O(nlogn)，空间复杂度O(n))而言，十分节约内存，但排序速度稍慢。在内存紧张且需要排序稳定的场合，原地稳定排序可以发挥其特长。
在介绍原地稳定排序的原理之前，需要先了解两个基本算法，旋转和二分查找。
a) 旋转
旋转又称循环移动，假设有这样一个序列：e0, e1, …, ei-1, ei, ei+1, …, en-1, en。现在我们需要把它向左循环移动i个位置变成：ei, ei+1, …, en-1, en, e0, e1, …, ei-1。为了尽可能的节约内存和保证较快的速度，我们可以在时间复杂度O(n)，空间复杂度O(1)的情况下达到目的。一种解决方案如下：
把原始序列看成两个子序列：e0, e1, …, ei-1和ei, ei+1, …, en-1, en
把这两个子序列分别逆序得：ei-1, …, e1, e0和en, en-1, …, ei+1, ei
也就是得到了这样一个序列：ei-1, …, e1, e0, en, en-1, …, ei+1, ei
再把上面的序列整体逆序得：ei, ei+1, …, en-1, en, e0, e1, …, ei-1
以上旋转过程的时间复杂度为O(n/2) + O(n/2) + O(n) = O(2n) = O(n)，逆序时仅需要一个元素的辅助空间，空间复杂度O(1)。
b) 二分查找
二分查找比较简单，在前面的二分插入排序算法里使用了二分查找获得上界(假设序列升序，序列中最后一个相同值的下一个位置或没有相同值时刚好比它大的那一个元素位置)。这里看看怎么使用二分查找获得下界(假设序列升序，序列中第一个相同值的位置或没有相同值时刚好比它小的那一个元素位置)。
下面以整数为例，看看怎么获得下界。
假设在一个有序序列10, 12, 12, 13, 13, 13 14, 14, 17, 17, 18, 19, 19中查找16。
该序列长度为13，找到中间值14，它比16小，查找的子序列长度降为6，在子序列[14, 19]中继续查找。找到中值18，它比16大，查找的子序列长度降为3，在子序列[14, 17]中继续查找。找到中值17，它比16大，查找的子序列长度降为1，在子序列[14, 14]中继续查找，找到14，它比16大，查找的子序列长度降为0，查找失败。返回14后面的元素位置，即第一个17的位置。
使用二分查找的前提条件是待查序列必须有序。无论查找上界还是下界，以及是否查找成功，二分查找的时间复杂度为O(logn)。或许有些读者在有的书上见过有的二分查找算法既不获得确定的上界也不获得确定的下界，可惜这样的二分查找算法除了考试以外似乎没有多大实用价值。
c) 原地稳定排序的原理
以整数为例，假设有一个需要稳定排序的无序序列：
52, 50, 50, 74, 61, 46, 84, 85, 73, 23, 94, 53, 97, 98, 65, 87, 29
首先需要把较长的序列使用插入排序分成多个有序的短序列。上面的序列可以分成两个子序列，然后分别进行插入排序，得到：
46, 50, 50, 52, 61, 74, 84, 85, 23, 29, 53, 65, 73, 87, 94, 97, 98
在前段[46, 85]查找后段[23, 98]的中值得73，返回74，这样后段[23, 98]的前部分[23, 65]中的任何元素比前段[46, 85]的后部分[74, 85]任何元素都小，旋转这两部分，得到：
46, 50, 50, 52, 61, 23, 29, 53, 65, 74, 84, 85, 73, 87, 94, 97, 98
在[23, 85]中查找[46, 61]的中值50，返回53，旋转[50, 61]和[23, 29]，得到：
46, 50, 23, 29, 50, 52, 61, 53, 65, 74, 84, 85, 73, 87, 94, 97, 98
在[46, 50]之间查找29，返回46，旋转得到：
23, 46, 50, 29, 50, 52, 61, 53, 65, 74, 84, 85, 73, 87, 94, 97, 98
在[29, 29]之间查找50，返回50，旋转得到：
23, 29, 46, 50, 50, 52, 61, 53, 65, 74, 84, 85, 73, 87, 94, 97, 98
在[53, 65]之间查找52，返回53，旋转，得到：
23, 29, 46, 50, 50, 52, 53, 61, 65, 74, 84, 85, 73, 87, 94, 97, 98
在[74, 85]之间查找94，返回73，在[73, 87]之间查找84，返回87，旋转得到：
23, 29, 46, 50, 50, 52, 53, 61, 65, 74, 73, 84, 85, 87, 94, 97, 98
交换73 和74，最终排序完毕。
23, 29, 46, 50, 50, 52, 53, 61, 65, 73, 74, 84, 85, 87, 94, 97, 98
1 // cycly moving left middle - first vacancies
2 template<typename RandomIterator>
3 void rotate(RandomIterator first, RandomIterator middle, RandomIterator last)
4 {
5 if(first == middle || last == middle) return;
6 reverse(first, middle);
7 reverse(middle, last);
8 while(first != middle && middle != last)
9 {
10 swap(*first, *--last);
11 ++first;
12 }
13 if(first == middle)
14 reverse(middle, last);
15 else
16 reverse(first, middle);
17 }
18
19 // find the lower bound, the returned value is the address of that bound
20 template <typename RandomIterator, typename T, typename Compare>
21 RandomIterator lower_bound(RandomIterator first, RandomIterator last,
22 const T& value, Compare cmp)
23 {
24 int len = last - first, half;
25 RandomIterator middle;
26 while(len > 0)
27 {
28 half = len >> 1;
29 middle = first + half;
30 if(cmp(*middle, value))
31 {
32 first = middle;
33 ++first;
34 len = len - half - 1;
35 }
36 else
37 len = half;
38 }
39 return first;
40 }
41
42 // find the upper bound, the returned value is the address of that bound
43 template <typename RandomIterator, typename T, typename Compare>
44 RandomIterator upper_bound(RandomIterator first, RandomIterator last,
45 const T& value, Compare cmp)
46 {
47 int len = last - first, half;
48 RandomIterator middle;
49
50 while(len > 0)
51 {
52 half = len >> 1;
53 middle = first + half;
54 if(cmp(value, *middle))
55 len = half;
56 else
57 {
58 first = middle;
59 ++first;
60 len = len - half - 1;
61 }
62 }
63 return first;
64 }
1 // no heap memory needed to merge two sequence
2 template <typename RandomIterator, typename Compare>
3 void merge_without_buffer(RandomIterator first, RandomIterator middle,
4 RandomIterator last, int len1, int len2, Compare cmp)
5 {
6 if(0 == len1 || 0 == len2) return;
7 if(2 == len1 + len2)
8 {
9 if(cmp(*middle, *first)) swap(*first, *middle);
10 return;
11 }
12 RandomIterator first_cut = first, second_cut = middle;
13 int len11 = 0, len22 = 0;
14 if(len1 > len2)
15 {
16 len11 = len1 >> 1;
17 first_cut += len11;
18 second_cut = lower_bound(middle, last, *first_cut, cmp);
19 len22 = second_cut - middle;
20 }
21 else
22 {
23 len22 = len2 >> 1;
24 second_cut += len22;
25 first_cut = upper_bound(first, middle, *second_cut, cmp);
26 len11 = first_cut - first;
27 }
28 rotate(first_cut, middle, second_cut);
29 RandomIterator new_middle = first_cut + (second_cut - middle);
30 merge_without_buffer(first, first_cut, new_middle, len11, len22, cmp);
31 merge_without_buffer(new_middle, second_cut, last, len1 - len11, len2 - len22, cmp);
32 }
33
34 // inplace merge sort
35 template <typename RandomIterator, typename Compare>
36 void inplace_merge_sort(RandomIterator first, RandomIterator last, Compare cmp)
37 {
38 if(last - first < 17)
39 {
40 insertion_sort(first, last, cmp);
41 return;
42 }
43 RandomIterator middle = first + ((last - first) >> 1);
44 inplace_merge_sort(first, middle, cmp);
45 inplace_merge_sort(middle, last, cmp);
46 merge_without_buffer(first, middle, last, middle - first, last - middle, cmp);
47 }
以上代码实现中用到了直接插入排序，该部分内容见本主页的快排介绍。