合併排序

合併排序是遵循分而治之的方法。 考慮一下，假設有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