归并排序

归并排序

一个归并排序的例子:对一个随机点的链表进行排序
分類	排序算法
數據結構	数组
最差時間復雜度	$\Theta(n\log n)$
最優時間復雜度	$\Theta(n)$
平均時間復雜度	$\Theta(n\log n)$
最差空間復雜度	$\Theta(n)$
最佳算法	有时是

归并排序（Merge sort，台灣譯作：合併排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

算法描述

归并操作的过程如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

示例代碼

以下示例代碼實現了歸併操作。array[]是元素序列，其中從索引p開始到q位置，按照升序排列，同時，從(q+1)到r也已經按照升序排列，merge()函數將把這兩個已經排序好的子序列合併成一個排序序列。結果放到array中。

C語言

//#只完成兩段之間歸併的功能#%
void Merge(int a[], int b[], int low, int mid, int high)
{
    int k = low;
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] <= a[begin2])
            b[k++] = a[begin1++];
        else
            b[k++] = a[begin2++];
    }
    if(begin1 <= end1)
        for(int q = begin1; q <= end1; q++)
            b[k++] = a[q];
    else
        for(int q = begin2; q <= end2; q++)
            b[k++] = a[q];
}
 
void MergePass(int a[], int b[], int seg, int size)
{
    int seg_start_ind = 0;
    while(seg_start_ind <= size - 2 * seg) //#size - 2 * seg的意思是滿足可兩兩歸併的最低臨界值#%
    {
        Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, seg_start_ind + seg * 2 - 1);
        seg_start_ind += 2 * seg;
    }
    //#如果一段是正好可歸併的數量而另一段則少於正好可歸併的數量#%
    if(seg_start_ind + seg < size)
        Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, size - 1);
    else
        for(int j = seg_start_ind; j < size; j++) //#如果只剩下一段或者更少的數量#%
            b[j] = a[j];
}
 
void MergeSort(int a[], int size)
{
    int* temp = new int[size];
    int seg = 1;
    while(seg < size)
    {
        MergePass(a, temp, seg, size);
        seg += seg;
        MergePass(temp, a, seg, size);
        seg += seg;
    }
}
 
int main()
{
    int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4}; //#QQ#%
    MergeSort(a, sizeof(a) / sizeof(*a));
    //#輸出#%
    for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
        cout << a[i] << ' ';
    cout << endl;
 
    return 0;
}

Ruby

def merge(left, right)
        final = []
        until left.empty? or right.empty?
                final << ( left.first < right.first ? left.shift : right.shift )
        end
        final + left + right
end

Java

public int[] Two_Way_Merge_Sort(int[] A, int[] B) {
        int[] C = new int[A.length + B.length];
        int k = 0;
        int i = 0;
        int j = 0;
        while(i < A.length && j < B.length) {
                if (A[i] < B[j])
                        C[k++] = A[i++];
                else
                        C[k++] = B[j++];
        }
        while (i < A.length) 
                C[k++] = A[i++];
        while (j < B.length) 
                C[k++] = B[j++];
        return C;
}

Python

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    if (i < len(left)):
        result.extend(left[i:])
    if (j < len(right)):
        result.extend(right[j:])
    return result
def mergesort(L):
    print(L)
    if len(L) < 2:
        return L[:]
    else:
        middle = int( len(L)/2 )
        left = mergesort(L[:middle])
        right = mergesort(L[middle:])
        answer = merge(left, right)
        print('merge:',answer)
        return answer
#use a list test the mergesort wrok
import random
testlist = []
#list with 10 element number (int) by random
for i in range(10):
    testlist.append(random.randint(0, 50))
print(testlist)
print('final:',mergesort(testlist))

归并排序

归并排序具体工作原理如下（假设序列共有n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成$floor(n/2)$个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成$floor(n/4)$个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

示例代码

示例代码为C语言，输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。调用完成后，array[]中从first到last处于升序排列。

void merge_sort(int array[], unsigned int first, unsigned int last)
{
        int mid = 0;
        if(first<last)
        {
                /*mid = (first+last)/2;*/ /*注意防止溢出*/
                /*mid = first/2 + last/2;*/
                mid = (first & last) + ((first ^ last) >> 1);
                merge_sort(array, first, mid);
                merge_sort(array, mid+1,last);
                merge(array,first,mid,last);
        }
}

相应的Ruby语言的例子，通过调用归并操作的merge方法，共同完成完整的归并排序功能。

def mergeSort(array)
        return array if array.size < 2
        left = array.first(array.size/2)
        right = array.last(array.size - array.size/2)
        merge(mergeSort(left), mergeSort(right))
end

相应的Javascript语言的例子，通过调用归并操作merge方法：

Array.prototype.mergeSort=function(array){
                var merge=function(left,right){
                                var final=[];
                                while (left.length  && right.length) {
                                        final.push(left[0] <= right[0] ? left.shift() : right.shift() );
                                }
                                return final.concat(left.concat(right));
                }//end of the merge
 
                if (this.length < 2) {
                        return this;
                }
                var _left=this.slice(0,parseInt(this.length/2));
                var _right=this.slice(parseInt(this.length/2));
                return merge(_left.mergeSort(),_right.mergeSort());
    }

用法如下： a=[7,7,11,19,13,14,333,134,256,2,3] a.mergeSort() 通过alert(a.mergeSort())可查看排序结果。

算法复杂度

比较操作的次数介于$(n log n)/2$和$n log n - n + 1$。 赋值操作的次数是$(2nlogn)$。 归并算法的空间复杂度为：Θ (n)

外部連結

• Dictionary of Algorithms and Data Structures: Merge sort
• Power Programming - Merge Sort
• Merge Sort Algorithm Simulation
• Mergesort For Linked Lists