# 合并排序

## 合并排序的实现

```/*C++ Implementation of Merge Sort*/
#include<bits/stdc++.h>
#define max_v 100000
using namespace std;
void add_subproblems(int a[],int l,int mid,int r)
{
int start_1=l;//starting index of subproblem 1;
int start_2=mid+1;//strating index of subproblem 2;
int store=l;//used to store the no in array a with O(1) space complexity.
/*compare the element from begining of both subproblems and choose the minimum element from them
and increment the index wrt minimum value by 1.*/
while(start_1<=mid&&start_2<=r)
{
if((a[start_1]%max_v)<=(a[start_2]%max_v))
{
a[store]+=(a[start_1]%max_v)*max_v;
store++;
start_1++;
}
else
{
a[store]+=(a[start_2]%max_v)*max_v;
store++;
start_2++;
}
}
/*if some elements are remaining in subproblem 1*/
while(start_1<=mid)
{
a[store]+=(a[start_1]%max_v)*max_v;
store++;
start_1++;
}
/*if some elements are remaining in subproblem 2*/
while(start_2<=r)
{
a[store]+=(a[start_2]%max_v)*max_v;
store++;
start_2++;
}
/*now change the elements into their oroginal values*/
for(int i=l;i<=r;i++)
{
a[i]/=max_v;
}
}
void merge(int a[],int l,int r)
{
if(l<r)
{
int mid=(l+r)/2;
merge(a,l,mid);
merge(a,mid+1,r);
}
}
int main()
{
int number;
/*total numbers which we want to sort*/
cin>>number;
int a[number];
/*take input*/
for(int i=0;i<number;i++)
{
cin>>a[i];
}
cout<<"Array before sorting: ";
/*print the array*/
for(int i=0;i<number;i++)
{
cout<<a[i]<<" ";
}
cout<<"\n";
/*call merge function*/
merge(a,0,number-1);
cout<<"Array after sorting: ";
/*print the array*/
for(int i=0;i<number;i++)
{
cout<<a[i]<<" ";
}
cout<<"\n";
return 0;
}```
```10
9 1 4 2 5 3 7 2 6 17```
```Array before sorting: 9 1 4 2 5 3 7 2 6 17
Array after sorting: 1 2 2 3 4 5 6 7 9 17```

## 时间复杂度

O（N * log N） 其中N是数组中存在的总数。 上述实现的重复关系为 T（N）= 2 * T（N / 2）+ O（1）.

## 空间复杂度

O（1） 在这里，除了给定数组之外，我们没有创建任何额外的空间，因此，空间复杂度是O（1），它是恒定的。