Merge sort template

Title Description :

  The code is as follows ：

#include <iostream>

using namespace std;

const int N = 100010;

int n, a[N], q[N];

void merge_sort(int l, int r)
{
	if(l >= r) return ;
	int mid = l + r >> 1;
	
	merge_sort(l, mid), merge_sort(mid + 1, r);
	
	int i = l, j = mid + 1, t = 0;
	while(i <= mid && j <= r)
	{
		if(a[i] >= a[j]) q[t ++ ] = a[j ++ ];
		else q[t ++ ] = a[i ++ ];
	}
	
	while(i <= mid) q[t ++ ] = a[i ++ ];
	while(j <= r) q[t ++ ] = a[j ++ ];
	
	for(i = l, j = 0; i <= r; i ++, j ++ )
	a[i] = q[j];
}

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

Extended topics : Reverse order to quantity

subject ：

  Ideas ： When the two ways merge, the two sequences will be orderly , At this point, it can be in the process of merging , Carry out statistical reverse order pair , Then the complexity will become nlog(n), See the code for details

// topic 4
#include <iostream>

using namespace std;

const int N = 1e6;

int n, a[N], q[N];
long long res = 0;

void merge_sort(int l, int r)
{
	if(l >= r) return ;
	
	int mid = l + r >> 1;
	merge_sort(l, mid), merge_sort(mid + 1, r);
	
	int i = l, j = mid + 1, t = 0;
	while(i <= mid && j <= r)
	{
		if(a[i] <= a[j])
		q[t ++ ] = a[i ++ ];
		else
		{
			res += mid - i + 1;                   // The core 
			q[t ++ ] = a[j ++ ];
		}
	}
	
	while(i <= mid) q[t ++ ] = a[i ++ ];
	while(j <= r) q[t ++ ] = a[j ++ ];
	
	for(int i = l, j = 0; i <= r; i ++, j ++ )
	a[i] = q[j];
}

int main()
{
	cin >> n;
	for(int i = 0; i < n; i ++ ) cin >> a[i];
	
	merge_sort(0, n - 1);
	
	cout << res << endl;
	return 0;
}

over