归并排序（简单讲解）

排序有许多种方法，其中最为简单的sort排序与冒泡排序，但是在一些需要排序的题目中这两个方法就不好用了。

例如洛谷P1908需要用到归并排序，今天我们来简单讲解一下这个排序方法。

首先我们需要明白，归并排序其实和二分有些相似的地方，具体如图

需要依次将一个数组分成单个后，比较大小，再次合并成为一个新的且排好顺序的数组

那么我们要攻克的难点为

1 将数组依次分开

2 排序

3 合并

分开时要用到二分的思想，当左端点小于右端点时进行分割，直到将整个数组分成单个数字存在，随后进行排序与合并

if(left<right)
	{
		int mid=(left+right)>>1;
		mmsort(arr,add,left,mid);
		mmsort(arr,add,mid+1,right);
		gb(arr,add,left,mid,right);
	}

这里我将排序与合并写在了一起，先存入左端点与右端点，方便后续将数据存入新数组，随后在循环中将此时要判断数据放入新数组中，最后将还没有存完的数组一起放在新数组的尾端，最后将新数组中的数据覆盖原数组

int l=left,r=mid+1;
	int pp=left;
	while(l<=mid&&r<=right)
	{
		if(arr[l]<arr[r])
		{
			add[pp++]=arr[l++];
		}
		else
		{
			add[pp++]=arr[r++];
		}
	}
	while(l<=mid)
	{
		add[pp++]=arr[l++];
	}
	while(r<=right)
	{
		add[pp++]=arr[r++];
	}
	while(left<=right)
	{
		arr[left]=add[left];
		left++;
	}

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
int arr[200000];
void gb(int arr[],int add[],int left,int mid,int right)
{
	int l=left,r=mid+1;
	int pp=left;
	while(l<=mid&&r<=right)
	{
		if(arr[l]<arr[r])
		{
			add[pp++]=arr[l++];
		}
		else
		{
			add[pp++]=arr[r++];
		}
	}
	while(l<=mid)
	{
		add[pp++]=arr[l++];
	}
	while(r<=right)
	{
		add[pp++]=arr[r++];
	}
	while(left<=right)
	{
		arr[left]=add[left];
		left++;
	}
}
void mmsort(int arr[],int add[],int left,int right)
{
	if(left<right)
	{
		int mid=(left+right)>>1;
		mmsort(arr,add,left,mid);
		mmsort(arr,add,mid+1,right);
		gb(arr,add,left,mid,right);
	}
}
void msort(int arr[],int n)
{
	int add[n+10];
	mmsort(arr,add,0,n-1);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i];
	}
	msort(arr,n);
	for(int i=0;i<n;i++)
	{
		cout<<arr[i]<<" ";
	}
	return 0;
 }