本文共 1333 字，大约阅读时间需要 4 分钟。

算法描述

归并排序使用递归分治的思想，先递归划分子问题，然后合并结果。假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序列表：再两两归并，…….,重复，直到得到一个长度为n的有序序列

1. 将所要进行排序的序列分为左右两部分，将要排序的序列起始元素下标赋给left, 最后一个元素下标赋给right
2. 将上面所得的两部分序列继续按照步骤1进行划分，直到划分的区间长度为1
3. 将划分结束后的序列进行归并排序，排序的方法为对所分的n个子序列进行两两合并，直到得到1个长度为n的有序序列

算法分析

空间复杂度：O(n)

/*C语言实现*/void merge(int arr[], int left, int mid, int right){    int i = left, j = mid + 1, k = 0;    //分配存储空间，用于存储合并后的数组    int *tmp = (int *)malloc(sizeof(int) * (right - left + 1)));    assert(tmp);    /*合并两个子序列*/    while(i <= mid && j <= right)    {        if(a[i] < a[j])        {            tmp[k] = a[i];            k++;            i++;        }        else        {            tmp[k++] = a[j++];            k++;            j++;        }    }    /*将其中一个剩余数据复制到临时数组*/    while(i <= mid)    {        tmp[k] = a[i++];        k++;        i++;    }    while(j <= right)    {        tmp[k] = a[j];        k++;        j++;    }    /**/    for(k = 0, i = left; i <= right; i++, k++)    {        a[i] = tmp[k];    }    free(tmp);    return;}void mergesort(int a[], int left, int right){    int mid = 0;    if(left < right)    //当左边小于右边，继续执行递归操作    {        mid = (left + right) / 2        mergesort(a, left, mid);        mergesort(a, mid + 1, right);        merge(a, left, mid, right);    }    else        return; /*递归终止*/}

转载地址：http://cboii.baihongyu.com/