# 归并排序 Merge Sort [译]

1.将每对单独的元素（默认情况下，已排序）合并为2个元素的排序数组（Merge each pair of individual element (which is by default, sorted) into sorted arrays of 2 elements,

2.将每对2个元素的排序数组合并为4个元素的排序数组， 重复这个过程...，（Merge each pair of sorted arrays of 2 elements into sorted arrays of 4 elements, Repeat the process...,

3.最后一步：合并2个N / 2个元素的排序数组（为了简化本讨论，我们假设N是偶数）来获得N个元素的完全排序数组。（Final step: Merge 2 sorted arrays of N/2 elements (for simplicity of this discussion, we assume that N is even) to obtain a fully sorted array of N elements.

This is just the general idea and we need a few more details before we can discuss the true form of Merge Sort.

We will dissect this Merge Sort algorithm by first discussing its most important sub-routine: The O(N) merge.

Given two sorted array, A and B, of size N1 and N2, we can efficiently merge them into one larger combined sorted array of size N = N1+N2, in O(N) time.

This is achieved by simply comparing the front of the two arrays and take the smaller of the two at all times. However, this simple but fast O(N) merge sub-routine will need additional array to do this merging correctly. See the next slide.

-----子程序代码实现：

``````void merge(int a[], int low, int mid, int high) {
// subarray1 = a[low..mid], subarray2 = a[mid+1..high], both sorted
int N = high-low+1;
int b[N];        // discuss: why do we need a temporary array b?
int left = low, right = mid+1, bIdx = 0;
while (left <= mid && right <= high)       // the merging
b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
while (left <= mid) b[bIdx++] = a[left++];       // leftover, if any  ※...它解决了我的疑问
while (right <= high) b[bIdx++] = a[right++];       // leftover, if any
for (int k = 0; k < N; k++) a[low+k] = b[k];       // copy back
``````

Before we continue, let's talk about Divide(划分) and Conquer(合并) (abbreviated as D&C), a powerful problem solving paradigm.

Divide and Conquer algorithm solves (certain kind of) problem — like our sorting problem — in the following steps:
1.Divide step: Divide the large, original problem into smaller sub-problems and recursively solve the smaller sub-problems,
（将较大的原始问题划分为较小的子问题，并递归地解决较小的子问题，）
2.Conquer step: Combine the results of the smaller sub-problems to produce the result of the larger, original problem.
（结合较小子问题的结果，以产生较大的原始问题的结果。）

Merge Sort is a Divide and Conquer sorting algorithm.

（归并排序是一种分而治之的排序算法）

The divide step is simple: Divide the current array into two halves (perfectly equal if N is even or one side is slightly greater by one element if N is odd) and then recursively sort the two halves.（划分步骤很简单：将当前数组分成两半（如果N是偶数则完全相等，或者如果N是奇数，则一侧稍微大一个元素）然后递归地对两半进行排序。）

The conquer step is the one that does the most work: Merge the two (sorted) halves to form a sorted array, using the merge sub-routine discussed earlier.（合并步骤则是最有效的：使用前面讨论的合并子例程合并两个（已排序）的一半以形成一个有序数组。）

C++实现：

``````void mergeSort(int a[], int low, int high) {
// the array to be sorted is a[low..high]
if (low < high) {      // base case: low >= high (0 or 1 item)
int mid = (low+high) / 2;
mergeSort(a, low  , mid );   // divide into two halves (分成两半)
mergeSort(a, mid+1, high);    // then recursively sort them(然后递归地对他们进行排序)
merge(a, low, mid, high);   // conquer : the merge subroutine (合并子程序)
}
}
``````

Title - Artist
0:00