曾经有段时间研究过排序算法，可惜记不住，虽然看懂，但都忘了。

感觉 BG 的代码自明性已经很好了。如果知道 merge 算法，应该能自己看懂。

这种排序是不是一定要这么大的辅助空间？反正一般见这算法都是用在链表上。
STL的标准实现就不是递归的：是先拿出头两个排好序，然后再拿出次两个排好序，归成4个有序的；然后再两个两个拿，归成4个。两个4个的归成8个这样一直下去。由于用在链表上，只准备了32个辅助指针。最大可以归2的32还是64次方个元素。

我学习算法也是浅尝辄止， 很多的观点都是来源于书上。

归并排序的数组实现一定要辅助空间，辅助空间到底能够小到什么程度，
我想应该不是我关注的重点，这是科研人员做的事情，
很多算法要给出一个 形式化的数学分析真的很困难，既使是简单算法也会有复杂的特性，
况且我又没有学习过高等数学之类的，我就不丢人了。

辅助空间的大小与 两个数组中的较小者成正比的那种，比较好实现一点。
归并排序适合用链表实现， 不过我个人很少使用链式结构学习算法。
至于是否用递归实现，我觉得并不重要， 算法的本质是一样的。
递归是后序遍历分治树，非递归是自底向上 层序遍历分治树。
也可以用栈代替 递归，后序遍历分治树。

我个人觉得没必要在算法上太过纠缠，这样可能会让自己的境地很难堪，
我是不喜欢在这上面纠缠的，估计一下，实际的项目使用的 简单算法 与 复杂算法的 比例应该不会高于 1000 ：1，

最近被先前遗留下来的 bug折腾了两个星期，导致整个项目被拖的走不动路，确实有点难堪。
那些不赚钱的算法暂时放一放，还是先把钱挣到口袋再说

喷的有点多了， 不好意思~~



[ 本帖最后由 BlueGuy 于 2011-1-29 12:34 编辑 ]

程序不同效率就不同，我想NOIP普及组的题目对于你来说应该是很水，但是有些程序不得不用高效算法。比如NOIP2010导弹拦截，必须快排才能得出正确答案。

我很赞成你的观点，

#include <vector>
#include <math.h>
using namespace std;

template <class Comparable>
void mergeImproved( vector<Comparable> &a )
{
    int size = a.size();
    vector<Comparable> b( size );  // 唯一的临时数组
    int maxLayer = 1;
    for ( int items = 2; items < size; items *= 2, ++maxLayer );

    // for each layer, perform merge sort.
    for ( int curLayer = 0, items = 0; curLayer < maxLayer; ++curLayer )
    {
        items = int( pow( double( 2 ), double( curLayer ) ) );//功能：pow(x,y)返回x的y次幂

        // decide which array of a and b is input or output
        vector<Comparable> &in = ( curLayer % 2 == 0 ) ? a : b;
        vector<Comparable> &out = ( curLayer % 2 == 0 ) ? b : a;
       
        // for each left and right sub arrays on the block
        for ( int index = 0; index < size; index += ( 2 * items ) )
        {

            // fix the left array's first and last indices
            int first1 = index;
            int last1 = ( first1 + items - 1 < size - 1 ) ? first1 + items - 1 : size - 1;

            // fix the right array's first and last indices
            int first2 = ( last1 < size - 1 ) ? last1 + 1 : size;///////////////////////(size-1)
            int last2 = (first2 + items - 1 < size - 1 ) ? first2 + items - 1 : size - 1;

            // now merge them in one block
            int outIx = first1;
            for ( ; first1 <= last1 && first2 <= last2; ++outIx )
                out[outIx] = ( in[first1] < in[first2] ) ? in[first1++] : in[first2++];

            for ( ; first1 <= last1; ++first1, ++outIx )
                out[outIx] = in[first1];

            for ( ; first2 <= last2; ++first2, ++outIx )
                out[outIx] = in[first2];
        }
    }

    // in case the sort items are in the temporary array
    if ( maxLayer % 2 == 1 )
        a = b; // copy them back to the original

优化的归并排序

上面感觉很复杂，优化在那里

给个 STL 的实现吧。虽然是 C++ 的，但不影响学算法~ 摘自 g++4.4 我改了点。

  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    merge(list& __x)        // 前三行是C++里的模版定义，不用管。这个函数用来把 x 的元素归并到当前链表里。
    {                       // 归并之后 x 会变成一个空表。也就是说是挪进当前链表里来。
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 300. list::merge() specification incomplete
      if (this != &__x)    // 只有在 x 不是当前表时，函数才起作用。用于防止类似 merge(a, a) 这样的情况。
        {
          _M_check_equal_allocators(__x);    // 由于要挪进当前表。
                                            // 因此两个前提是两个表用要用相同的内存分配器.
          iterator __first1 = begin();
          iterator __last1 = end();
          iterator __first2 = __x.begin();
          iterator __last2 = __x.end();
          while (__first1 != __last1 && __first2 != __last2)
            if (*__first2 < *__first1)
              {
                iterator __next = __first2;
                _M_transfer(__first1, __first2, ++__next);  // transfer(a, b, c) 的意思是： 把指针 b, c 之间的内容(逻辑上它们要指向同一个序列的前后元素)剪切到 a 的后面。
                __first2 = __next;
        }
            else
              ++__first1;
          if (__first2 != __last2)
            _M_transfer(__last1, __first2, __last2);
        }
    }

  template<typename _Tp, typename _Alloc>
    void
    list<_Tp, _Alloc>::
    sort()        // 这个是排序。
    {
      // Do nothing if the list has length 0 or 1.
      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
          && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
      { // list 是带头结点的双向循环链表。因此在头结点的后面是头结点(这种情况是空表)或者头结点后面的后面是头结点(这时只有一个元素)的时候，不进行排序。
        list __carry;    // carry 用来临时持有一个链表，以和tmp中的某一个进行归并。
        list __tmp[64];    // tmp[n] 用来持有一个长度为 2^n 次方个元素的链表。就是 tmp[0] 只能持有一个元素。tmp[1] 持有两个。
        list * __fill = &__tmp[0]; // 用来记录用到的tmp的最大下标的链表。大于 fill 的tmp[n] 均是空表。初始化到0上。
        list * __counter;    // 顾名思义就是计数器，用于下面的循环。

        do // 在当前表不空前，不停地往 tmp 里按大小归并当前的链表。
          {
            __carry.splice(__carry.begin(), *this, begin());
            for(__counter = &__tmp[0];
                __counter != __fill && !__counter->empty();
                ++__counter)
              {
                __counter->merge(__carry);
                __carry.swap(*__counter);
              }
            __carry.swap(*__counter);
            if (__counter == __fill)
              ++__fill;
          }
        while ( !empty() ); 

        // 然后把 tmp 里所有长度的表都归并到 fill-1 这个表里。这个过程不再受tmp[n]的长度限制。
        for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
          __counter->merge(*(__counter - 1));

        // 最后把 fill-1 换回当前链表。
        swap( *(__fill - 1) );
      }
    }

基本上只是介绍一下思路。代码还得大家自己琢磨。

[ 本帖最后由 pangding 于 2011-1-29 11:52 编辑 ]

void mergeSort(int a[], int left, int right)
{
    int i, mid;

    for (mid = 1; mid <= right-left; mid += mid)
    {
        for(i = left; i <= right-mid; i += mid+mid)
        {
            merge(a, i, i+mid-1, min(i+mid+mid-1, right));
        }
     }
}

这个是 归并排序的 非递归版本， 算法书籍我看过几本，这种小儿科程序表以为我不知道。

NOIP不允许加STL。。。