归并排序是颇受欢迎的排序算法，因为他的时间复杂度恒为O(n log(n))。顾名思义，这个排序算法就是将多个排好序的数组合并成单个排好序的数组。

具体步骤如下：

• 将待排序的数组分成左右两部分。
• 再将这两部分分别分成左右两部分。
• 一直分下去，直到不可分（每部分只有一个元素）。
• 由于数组被分成许多的单个数据，比较起来就简单了，然后开始合并，合并的同时排序。
• 持续合并直到得到排好序的数组。

下面这幅图可以帮助你理解算法过程：

上图中可以看到，算法将数组分为两个部分，然后再分，一直分到只有一个元素，然后合并成已排序的数组。

将两个已排序的数组合并成一个排序的数组的方法在前面已经讨论过了，不清楚的同学看一下

归并排序显然可以用分治法，算法如下：

# split in half

m = n / 2

# recursive sorts

sort a[1..m]

sort a[m+1..n]

# merge sorted sub-arrays using temp array

b = copy of a[1..m]

i = 1, j = m+1, k = 1

while i <= m and j <= n,

    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]

→ invariant: a[1..k] in final position

while i <= m,

    a[k++] = b[i++]

→ invariant: a[1..k] in final position

算法实现：

#include
     
       //defining a function to merge 2 sorted arrays//note that the 2 arrays will be contained in a single array//as the left and right partvoid merge(int arr[], int start, int mid, int end){    // the array is as:- {start, ... ..mid, mid+1, .....end}    // thus there are 2 arrays we need to merge     //1st array , starting index and last index    int i = start;    int l1 = mid;     //2nd array , starting index and last index    int j = mid+1;    int l2 = end;     //create an auxiliary array to store the elements    int len = end-start + 1;    int *arr2 = (int *)malloc(sizeof(int)*len);    int k = 0;     //apply the algorithm to merge 2 sorted arrays    while(i<=l1 && j<=l2)    {        if(arr[i] < arr[j])            arr2[k++] = arr[i++];        else            arr2[k++] = arr[j++];    }     while(i<=l1)        arr2[k++] = arr[i++];    while(j<=l2)        arr2[k++] = arr[j++];     //copy the auxiliary array to original array    for(k = 0; k
     

Time Complexity: O(n log(n)) for all cases

Space Complexity: O(n) for the Sortauxiliary array