STL源码分析: list的sort函数

本是古典何须时尚 2023-06-13 13:26 7阅读 0赞

今天，来看看STL里面的sort函数，这个排序函数真是让人眼前一亮啊，有趣的很~·

很奇怪的是里面居然硬编码了一个counter\[64\]??? 一个很naive的怀疑就是，这玩意的长度是硬编码进去的不会越界嘛？？？？

其实现为：

template <class T, class Alloc>
    void list<T, Alloc>::sort() { 
      if (node->next == node || link_type(node->next)->next == node) return;
      list<T, Alloc> carry;
      list<T, Alloc> counter[64];
      int fill = 0;
      while (!empty()) { 
        carry.splice(carry.begin(), *this, begin());
        int i = 0;
        while(i < fill && !counter[i].empty()) { 
          counter[i].merge(carry);
          carry.swap(counter[i++]);
        }
        carry.swap(counter[i]);         
        if (i == fill) ++fill;
      } 
    
      for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
      swap(counter[fill-1]);
    }

其中，先看看排序过程中涉及到的函数的实现：

*  splice函数：

void splice(iterator position, list&, iterator first, iterator last) { 
        if (first != last) 
          transfer(position, first, last);
      }

而transfer(position,first,last)函数则是把list双向循环链表里面由迭代器fist,last确定的一个左闭右开区间\[first,last)的元素都挂在position迭代器的前面。  
例如一个list: \[5,4,2,7,10\],position指向4,first 指向2，last指向10。transfer调用后得到：\[5,2,7,4,10\]。

splice就是对transfer一个简单的封装。

*  merge

template <class T, class Alloc> template <class StrictWeakOrdering>
    void list<T, Alloc>::merge(list<T, Alloc>& x, StrictWeakOrdering comp) { 
      iterator first1 = begin();
      iterator last1 = end();
      iterator first2 = x.begin();
      iterator last2 = x.end();
      while (first1 != last1 && first2 != last2)
        if (comp(*first2, *first1)) { 
          iterator next = first2;
          transfer(first1, first2, ++next);
          first2 = next;
        }
        else
          ++first1;
      if (first2 != last2) transfer(last1, first2, last2);
    }

merge函数负责把当前的list和参数指定的list进行合并，这两个list都得是排好序的。merge的结果是把参数 x 链表的元素有序的合并到当前的list上。

*  swap函数

void swap(list<T, Alloc>& x) {  __STD::swap(node, x.node); }

swap函数负责，把当前链表的头节点和目标链表的头节点进行互换。

*  STL list的结构  
    在STL中list就是一个双向的循环链表，每个list有一个表头节点node ，这个节点的数据域不发挥左右，只用于跟踪当前的链表。  
    它的结构类似于下图：反正就是个双向的循环链表。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]

OK.相关函数就是上面这些，我们分析这个sort函数。

侯捷的书上说它是个快排，然而实际上这个怎么看也不是快排。它的行为其实有点像归并的。

我们先初始化一个list: \[5,3,7,8,2,6,9,5\]，在内部是这么一个双向链表结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 1]

OK,我们给源代码各行标个序，便于分析。我们把上面那个链表代入进入调用sort看会里面是怎么一回事。

template <class T, class Alloc>
    void list<T, Alloc>::sort() { 
      1.if (node->next == node || link_type(node->next)->next == node) return;
      2.list<T, Alloc> carry;
      3.list<T, Alloc> counter[64];
      4.int fill = 0;
      5.while (!empty()) { 
      6.  carry.splice(carry.begin(), *this, begin());
      7.  int i = 0;
      8.  while(i < fill && !counter[i].empty()) { 
      9.    counter[i].merge(carry);
      10.    carry.swap(counter[i++]);
      11.  }
      12.  carry.swap(counter[i]);         
      13.  if (i == fill) ++fill;
      } 
    
      14.for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
      15.swap(counter[fill-1]);
    }

首先第1行，检查链表是不是空或者只有一个有效的元素。如果空或只有一个元素的话，那就不用排序了，自然而然就是有序的。  
第2,3行定义两个局部变量carry,counter。他们都是同类型的list变量。而且counter还是个硬编码长度的List数组。  
第5-13行是个大循环。循环的进入条件是当前的list不为空。我们的list包含8个元素，可以进入循环。  
第6、7行，把list的第一个元素给carry.此时：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>5</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[3,7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第8行，i为0而且counter\[0\]也为空，于是不进去内层循环。  
第12行，carry和counter\[0\]交换表头节点。结果为：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[3,7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第13行，i等于fill，于是fill自增，表示counter数组里面已经有一个元素被占坑了。

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[3,7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

--------------------

又回到第5行，看当前链表是否为空，显然目前`*this` 还有7个元素，当然不为空，进入循环。  
第6行，carry得到\*this的首元素。  
第7行，i为0.此时：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[3]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第8行，此时i<fill而且counter\[i\]是有元素的，于是进入内层循环。  
第9行，把carry包含的元素合并到counter\[i\]里面。

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[0]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[i]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第10行，再把新合并的counter\[i\]给carry,同时让i自增。

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

在回第8行，发现此时内循环条件不成立，跳出内循环。  
第12行，把carry给counter\[i\]。即：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第13行，更新fill,表示counter数组里面已经填过2个两个元素了。

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[7,8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

--------------------

又回到第5行，看当前链表是否为空，显然目前`*this` 还有6个元素，当然不为空，进入循环。  
第6行，carry得到\*this的首元素。  
第7行，i为0.此时：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[7]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第8行，此时i<fill,但是counter\[i\]是没有元素的，于是不进入内层循环。

第12行，把carry给counter\[i\]。即：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[8,2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[7]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

--------------------

又回到第5行，此时当前链表还有5个元素，当然进入循环。  
第6，7行，把当前链表第一个元素给carry。

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[7]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第8行，i<fill,而且counter\[i\]有一个元素，进入内循环。  
第9行，把carry合并到counter\[i\]

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第10行，再把counter\[i\]给carry，同时让i自增。

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[7，8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

回到第8行，发现此时i<fill,而且counter\[i\]有两个元素，于是进入再次进入循环。  
第9行，把carry和counter\[i\]合并，得到：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第10行，再把counter\[i\]给carry,同时让i自增。

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[3,5，7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

回到第8行，不满足条件。  
第12行，把carry给counter\[2\].

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

第13行，把fill增大：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2,6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

OK,分析到这里，后面就是一样的套路了。  
把首元素给carry:

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[2]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

把carry给counter\[0\]

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[6,9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[2]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

把首元素给carry:

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[6]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[2]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

合并carry和counter\[0\],把合并结果挂到counter\[1\]去

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[9,5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[2,6]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

--------------------

把首元素给carry,

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[2,6]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

把carry挂到counter\[0\]

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[2,6]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

--------------------

把首元素给carry

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[5]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[2,6]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>0</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

把carry和counter\[0\]合并，

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[5，9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[2,6]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

把carry和counter\[1\]合并

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[2，5,6，9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[3,5,7,8]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>2</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

把carry和counter\[2\]合并

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[2，3，5,5，6，7，8，9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

把carry给counter\[3\],同时自增fill

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[3]</td> 
   <td>[2，3，5,5，6，7，8，9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>4</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>i</td> 
   <td>3</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

最后，第5行的条件不再满足。不进入循环。

14行，把相邻的两个counter\[i\]合并。  
最后，把counter\[fiil-1\]给\*this,  
于是得到：

<table> 
 <thead> 
  <tr> 
   <th>变量</th> 
   <th>内容</th> 
   <th>-</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>carry</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>*this</td> 
   <td>[2，3，5,5，6，7，8，9]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[0]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[1]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[2]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>counter[3]</td> 
   <td>[]</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>fill</td> 
   <td>4</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

总结

根据上面的分析，我们可以知道，sort函数设计思路是：counter\[i\] 维护当前最近遇到的元素里面  2 i 2^i 2i 个元素有序。当counter\[i\]需要接收超过 2 i 2^i 2i 个元素的时候，它就向上合并。遇到新的元素，先把它丢到counter\[0\]，如果发现counter\[0\]有一个元素，那么就把整个新的元素和原来的counter\[0\]里面的元素共两个元素合并，插入到counter\[1\],如果发现counter\[1\]也满了，就把counter\[1\]也一起拿出来合并，向上呈递。  
···  
通过这种方式，层层合并的方式，最后可以实现排序。  
均摊下来的时间复杂度为： O ( n l o g n ) O(nlogn) O(nlogn)，猜测。

另外值得一提的是，STL里面把counter数组长度硬编码为64，通过上面的分析是是绰绰有余的！！  
counter\[64\]可以接收 2 63 2^\{63\} 263个元素的排序，远远足够了·····

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191117164236930.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191117165753839.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ptaDE5OTY=,size_16,color_FFFFFF,t_70