之前用js写了个归并排序非递归版，而这一次，c++封装链表的时候也遇到了一个归并排序的接口。邓老师实现了递归版本的归并排序，但是递归的调用函数栈的累积是很占内存空间的。于是乎，那试试在链表结构上实现以下归并排序吧。但是一旦开始，就遇到难题了，在链表下，我们无法按索引访问，所以，在迭代过程中，左右序列就无法很好的用o（1）时间就解决。先看看我实现的代码吧，初步测试没问题，如果有什么问题，希望大神指出，不知为何，用c++写东西总觉得哪里有问题，即使程序可以运行。
template<typename T>
void List<T>::mergeSort(Posi(T) p, int n)
{
Posi(T) h = p->pred;
Posi(T) r_p;
for (int i = ; i < n; i*=)
{
p = h->next;
r_p = p;
int count = ;
while (count*<n)
{
int r_len = ;
while (r_len<i&&r_p!=trailer)
{
r_p = r_p->next;
r_len++;
count++; //右链表移动的次数
}
if (r_p == trailer)
{
break;
}
if (count*>n)
{
r_len = n%i;
}
p = merge(p, i, r_p, r_len);
r_p = p;
}
}
}
这是主干程序，大体思路是从一开始的一个一个归并并，到四个四个合并，到最后二路归并，一开始，因为这个接口是在给定位置的p点已经后面的n-1个元素进行排序，所以我无法直接使用header，于是，用p点的前一个左右目前头结点，为什么这么做呢，一开始的时候，我是打算用p左右每次迭代的开始，如果你对迭代版归并熟悉的话，那么应该很容易理解，每一次合并完所有链表上的分列表，都需要重新从第一个结点开始，然后继续合并下一个循环，而因为链表是动态的，很有可能，一次合并后，你的p就不是现在的第一个结点了，这是h变量的含义，他是一个头结点,当然，按照这个接口，尾结点也需要重新定义，然而定义尾结点需要n时间复杂度，所以这里，我的代码是假设n个的下一个刚好是尾结点。之后是需要合并的右链表的位置，一开始是和左链表重合，然后通过循环来达到它的位置，count变量是r_p走的步数，这个步数两倍是可能超过长度n的，一旦超过，说明了r_p时间上已经到达了末尾，这时候一个级数的合并已经完成，可以进入下一个迭代归并。
而r_len = n%i;的意义是如果越界,那么需要取得余数，是正好等于尾巴的长度。
如果不这么做，那么merge函数可能链表越界，接下来看看别的部件。
template<typename T>//包括p在内的n个元素
Posi(T) List<T>::merge(Posi(T) left_p, int left_len,Posi(T) right_p, int right_len)
{
while (left_len > &&right_len > )
{
if (left_p->data < right_p->data)
{
left_p = left_p->next;
left_len--;
}
else
{
Posi(T) temp_p = right_p->next;
insertAsPre(right_p, left_p);
right_p = temp_p;
right_len--;
}
}
while (right_len-->)
{
right_p = right_p->next;
}
return right_p;
}
template<typename T> //重写接口，以至于可以插入已有节点，同一个链表的节点
Posi(T) List<T>::insertAsPre(Posi(T) p, Posi(T) n)
{
p->next->pred = p->pred;
p->pred->next = p->next;
p->pred = n->pred;
p->next = n;
n->pred = p;
p->pred->next = p;
return p;
}
现在可以分析下这个算法的时间复杂度了。
最外层的for循环应该是logn，这个很好理解，而为了得到左指针的while循环必然是n/2，merge函数花费是n，while和merge同级，所以花费是3n/2.
如果算上这个接口尾指针。应该是o(3n/2*logn+n),整体是比数组的归并要慢一点，但是还是在同一个数量级的，这是值得开心的。