归并排序是一种稳定的算法，采用分治的思想，将有序的子序列合并得到有序的序列。具体的实现步骤为：
- 将序列分为长度为n/2的两部分
- 对有做两部分分别采用分治思想得到有序的序列
- 将有序的子序列合并得到有序序列
具体代码实现如下：
class Solution
{
void mergeSort(vector<int> & array)
{
if(array.empty()) return;
vector<int> temp(array.size());
mergeSortHelper(0, array.size() - 1);
return;
}
// partition -> merge过程重复调用，直到最小元素
void mergeSortHelper(vector<int> & array, int start ,int end)
{
//递归结束条件是star == end, 即最后一次合并直接合并两个数，具体的合并过程可以用二叉树模拟
if(start < end)
{
int mid = (start + end) >> 1;
mergeSortHelper(array,start,mid);
mergeSortHelper(array,mid+1,end);
mergeArray(array,start, mid,mid+1,end);
}
}
void mergeArray(vector<int> & array,int l1, int l2, int r1, int 2)
{
int i = l1, j = r1;
int n = (l2 - l1 + 1)*(r2 - r1 + 1);
vector<int> temp(n);
int k = 0;
while(i <= l2 && j <= r2)
{
if(array[i] < array[j])
temp[k++] = array[i++];
else
temp[k++] = array[j++];
}
while(i <= l2)
temp[k++] = array[i++];
while(j <= r2)
temp[k++] = array[j++];
for(int i = 0; i < n; ++i) //将临时数组元素拷贝到原始数组当中
array[l1 + i] = temp[i];
}
}
