原地歸并排序的時間復雜度為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 }
以上代碼實現中用到了直接插入排序，該部分內容見本主頁的快排介紹。