[2. merge sort]

Merging is different from fast sorting ：

Quick sort ：

• The dividing point is one of the random arrays Count Come to share , Make the left side all <= The number of , On the right >= The number of （ The number ）
• Finish first , On the two sides of recursion respectively

Merge sort ：

• First recurse both sides , In the process of merging
• The dividing point is The middle of the whole array ( Subscript value )

Ideas ：( Double pointer algorithm )

1. Determine the cut-off point mid = (l + r) / 2
2. Sort recursively, respectively , Left and right
3. At this point, after the recursion is completed , Both sides are ordered arrays , At this point, two arrays Become ( above all > Of )

Schematic diagram

(1) recursive （ Recursion from top to bottom ）

---

(2) Become （ Recursion is recursion from top to bottom , A merge is a bottom-up merge ）

subject

Give you a length of n The whole number sequence of .
Please use merge sort to sort this sequence from small to large .
And output the ordered sequence in order .


Input format
There are two lines of input , The first line contains integers n.
The second line contains n It's an integer （ All integers are in 1∼109 Within the scope of ）, Represents the whole sequence of numbers .


Output format
The output is one line , contain n It's an integer , It's an ordered sequence .


Data range
1 ≤ n ≤ 100000


sample input ：

5
3 1 2 4 5

sample output ：

1 2 3 4 5

Code

#include<iostream>
using namespace std;

const int N = 1000010;
int q[N];
int temp[N];                       // Defines another temporary array , So the space complexity is zero O(1);
int n;

void merage_sort(int q[],int l,int r)
{
     
   if(l>=r)return;
   int mid = l+r>>1;
  
   merage_sort(q, l, mid);        // recursive 
   merage_sort(q,mid+1, r);       // After recursion , At this point, it becomes two ordered sequences , Namely [l, >mid]  and  [mid+1, r].
  
   int k = 0;
   int i = l,j=mid+1;             // The starting elements of these two arrays are l and mid+1
   
   while(i<=mid && j<=r)          // When any one of the arrays is traversed , Stop program 
   {
     
      if(q[i]<=q[j])  temp[k ++] = q[i ++];
      else  temp[k ++] = q[j ++];
   }
   while(i<=mid)  temp[k ++] = q[i ++];    // At this point, an array has been traversed , And the other array has > The remaining , The rest are arranged in order , So just connect the following paragraph to temp On 
   while(j<=r)    temp[k ++] = q[j ++];
   
   for(int i =l ,j = 0;i<=r;i++,j++)q[i] = temp[j];   // This is a letter l, Not numbers 1, Set the value of the temporary array ,> After copying to the original array q in 
}

int main()
{
     
   scanf("%d",&n);
   for(int i = 0;i < n;i++)  scanf("%d",&q[i]);
   
   merage_sort(q,0,n-1);
   
   for(int i = 0;i<n;i++)  printf(" %d",q[i]);
   return 0;
}