排序之归并排序

 一、数据结构
        约定排序均为升序排序，要排序的记录存储在线性表中，线性表由排序关键字和其它域组成，其定义如下：
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型，比如int，float或char等，在算法中，约定其为int类型。

二、算法思想
        所谓归并排序就是将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。
        设有两个有序关键字表s1={18, 25, 37, 42}，s2={20, 33, 40}。同时s1和s2存储在数组r[1, 7]中，s1放r[1, 4]中，s2放r[5, 7]中，现要归并到一维数组r2[1, 7]之中。具体做法是，只要依次比较这两个有序表中相应记录关键字，按照“取小”原则复制到r2之中即可。

三、程序实现
        实现归并排序的函数如下：
        void mergesort(sqlist r, int 1, int m, int h, sqlist r2)        // r[1, m]及r[m+1, h]分别有序，归并后置于r2中      
        {
            int i, j, k;
            k = 1;                              // k是r2的指示器，i、j分别为s1、s2的指示器
            i = 1;
            j = m+1;
            while (i<=m && j<=h)  
            {
                if (r[i].key <= r[j].key)
                {
                    r2[k] = r[i];
                    i++;
                }
                else
                {
                    r2[k] = r[j];
                    j++;
                }
                k++;
            }
            if (i > m)                         // s1结束
            {
                while (j <= h)
                {
                    r2[k] = r[j];            // 将s2复制到r2
                    j++;
                    k++;
                }
            }
            else
            {
                while (i <= m)
                {
                    r2[k] = r[i];            // 将s1复制到r2
                    i++;
                    k++;
                }
            }
        }
        归并排序算法的时间复杂度是O(nlog₂n)，它是一种稳定的排序方法。