合併排序

合併排序是遵循分而治之的方法。 考慮一下，假設有n個元素的陣列A。該演算法分3個步驟處理元素。

1. 如果A包含0或1個元素，則它已經被排序，否則，將A分成兩個具有相同數量元素的子陣列。
2. 使用合併排序遞回地對兩個子陣列進行排序。
3. 組合子陣列以形成單個最終排序陣列，維護陣列的順序。

合併排序背後的主要思想是，短列表需要較少的時間進行排序。

複雜度

範例：
考慮以下7個元素的陣列，使用合併排序對陣列進行排序。

A = {10, 5, 2, 23, 45, 21, 7}

演算法

第1步 : [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
第2步 : 當(I <= MID) AND (J<=END)時，迴圈執行
    IF ARR[I] < ARR[J]
        SET TEMP[INDEX] = ARR[I]
        SET I = I + 1
    ELSE
        SET TEMP[INDEX] = ARR[J]
        SET J = J + 1
    [IF結束]
    SET INDEX = INDEX + 1
    [結束回圈]
第3步 : [複製右子陣列的其餘元素(如果有的話)]
    IF I > MID
    當 while J <= END時，迴圈
        SET TEMP[INDEX] = ARR[J]
        SET INDEX = INDEX + 1, SET J = J + 1
        [結束回圈]
        [複製右子陣列的其餘元素(如果有的話)]
    ELSE
        當 while I <= MID 時，迴圈
        SET TEMP[INDEX] = ARR[I]
        SET INDEX = INDEX + 1, SET I = I + 1
    [迴圈結束]
    [IF結束]
第4步 : [將TEMP的內容複製回ARR] SET K = 0
第5步 : 當 while K < INDEX 時，迴圈
    SET ARR[K] = TEMP[K]
    SET K = K + 1
[結束回圈]
第6步 : 退出

MERGE_SORT(ARR，BEG，END)

第1步：IF BEG <END
    SET MID =(BEG + END)/ 2
    CALL MERGE_SORT(ARR，BEG，MID)
    CALL MERGE_SORT(ARR，MID + 1，END)
    MERGE(ARR，BEG，MID，END)
    [結束]
第2步：結束

使用C語言實現合併排序演算法，程式碼以下所示 -

#include<stdio.h>  
void mergeSort(int[],int,int);  
void merge(int[],int,int,int);  
void main ()  
{  
    int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
    int i;  
    mergeSort(a,0,9);  
    printf("printing the sorted elements");  
    for(i=0;i<10;i++)  
    {  
        printf("\n%d\n",a[i]);  
    }  

}  
void mergeSort(int a[], int beg, int end)  
{  
    int mid;  
    if(beg<end)  
    {  
        mid = (beg+end)/2;  
        mergeSort(a,beg,mid);  
        mergeSort(a,mid+1,end);  
        merge(a,beg,mid,end);  
    }  
}  
void merge(int a[], int beg, int mid, int end)  
{  
    int i=beg,j=mid+1,k,index = beg;  
    int temp[10];  
    while(i<=mid && j<=end)  
    {  
        if(a[i]<a[j])  
        {  
            temp[index] = a[i];  
            i = i+1;  
        }  
        else   
        {  
            temp[index] = a[j];  
            j = j+1;   
        }  
        index++;  
    }  
    if(i>mid)  
    {  
        while(j<=end)  
        {  
            temp[index] = a[j];  
            index++;  
            j++;  
        }  
    }  
    else   
    {  
        while(i<=mid)  
        {  
            temp[index] = a[i];  
            index++;  
            i++;  
        }  
    }  
    k = beg;  
    while(k<index)  
    {  
        a[k]=temp[k];  
        k++;  
    }  
}

執行上面範例程式碼，得到以下結果：

printing the sorted elements 

7
9
10
12
23
23
34
44
78
101

使用Java語言實現合併排序演算法，程式碼以下所示 -

public class MyMergeSort {
    void merge(int arr[], int beg, int mid, int end) {

        int l = mid - beg + 1;
        int r = end - mid;
        int LeftArray[];
        int RightArray[];
        LeftArray = new int[l];
        RightArray = new int[r];

        for (int i = 0; i < l; ++i)
            LeftArray[i] = arr[beg + i];

        for (int j = 0; j < r; ++j)
            RightArray[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = beg;
        while (i < l && j < r) {
            if (LeftArray[i] <= RightArray[j]) {
                arr[k] = LeftArray[i];
                i++;
            } else {
                arr[k] = RightArray[j];
                j++;
            }
            k++;
        }
        while (i < l) {
            arr[k] = LeftArray[i];
            i++;
            k++;
        }

        while (j < r) {
            arr[k] = RightArray[j];
            j++;
            k++;
        }
    }

    void sort(int arr[], int beg, int end) {
        if (beg < end) {
            int mid = (beg + end) / 2;
            sort(arr, beg, mid);
            sort(arr, mid + 1, end);
            merge(arr, beg, mid, end);
        }
    }

    public static void main(String args[]) {
        int arr[] = { 90, 23, 101, 45, 65, 23, 67, 89, 34, 23 };
        MyMergeSort ob = new MyMergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + "");
        }
    }
}

執行上面範例程式碼，得到以下結果：

Sorted array
23
23
23
34
45
65
67
89
90
101

使用C# 語言實現合併排序演算法，程式碼以下所示 -

using System;  
public class MyMergeSort  
{  
void merge(int[] arr, int beg, int mid, int end)  
{  

    int l = mid - beg + 1;  
    int r = end - mid;  
    int i,j;  

    int[] LeftArray = new int [l];  
    int[] RightArray = new int [r];  

    for (i=0; i<l; ++i)  
    LeftArray[i] = arr[beg + i];  

    for (j=0; j<r; ++j)  
    RightArray[j] = arr[mid + 1+ j];  

    i = 0; j = 0;  
    int k = beg;  
    while (i < l && j < r)  
    {  
        if (LeftArray[i] <= RightArray[j])  
        {  
            arr[k] = LeftArray[i];  
            i++;  
        }  
        else  
        {  
            arr[k] = RightArray[j];  
            j++;  
        }  
        k++;  
    }  
    while (i < l)  
    {  
        arr[k] = LeftArray[i];  
        i++;  
        k++;  
    }  

    while (j < r)  
    {  
        arr[k] = RightArray[j];  
        j++;  
        k++;  
    }  
}  

    void sort(int[] arr, int beg, int end)  
    {  
        if (beg < end)  
        {  
            int mid = (beg+end)/2;  
            sort(arr, beg, mid);  
            sort(arr , mid+1, end);  
            merge(arr, beg, mid, end);  
        }  
    }  
    public static void Main()  
    {  
        int[] arr = {90,23,101,45,65,23,67,89,34,23};  
        MyMergeSort ob = new MyMergeSort();  
        ob.sort(arr, 0, 9);  

        Console.WriteLine("\nSorted array");  
        for(int i =0; i<10;i++)  
        {  
            Console.WriteLine(arr[i]+"");  
        }  
    }  
}

執行上面範例程式碼，得到以下結果：

Sorted array 
23
23
23
34
45
65
67
89
90
101