归并排序是分治法的典型应用。基本思想是将一个数组分成左右两部分，对其分别排序，然后合并这两个有序数组，成为一个整个的有序数组。
合并两个有序数组也十分简单，两个指针分别指向两个有序数组的首地址，哪个数小，就将其移动到新数组中，直到两个数组为空，新数组就是合并后的有序数组，合并两个数组也称为二路归并。
归并排序是稳定的排序，即相等的元素的顺序不会改变。如果要排序数据包含多个信息，而要按其中的某一个信息排序，要求其它信息尽量按输入的顺序排列时很重要。这也是它比快速排序优势的地方。
void merge(int *arr1, int *arr2, int *result, int len1, int len2)
{
int i = 0;
int j = 0;
int k = 0;
while(i < len1 || j < len2)
{
if(j == len2 || arr1[i] < arr2[j])
{
result[k] = arr1[i];
i++;
k++;
}
else if(i == len1 || arr1[i] >= arr2[j])
{
result[k] = arr2[j];
j++;
k++;
}
}
}
void merge_sort(int *arr, int left, int right)
{
if(right < left)
{
int mid = (right + left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
int result[right - left];
merge(arr, arr + mid + 1, result, mid - left, right - mid - 1);
}
}