Algorithm idea:

Merge sort is a dime-and-conquer strategy, and the basic idea is that you divide an unordered sequence into smaller unordered sequences until there’s only one number in the sequence, and then you merge the sequence, which is an ordered sequence, until you merge it into the last number, which is merge sort.

Merge sort process:

  1. Select the middle of the sequence to begin splitting the sequence into two parts, the two sequences continue to merge sort.
  2. When there is only one number in the sequence, instead of splitting (because then the sequence of one number is ordered), the sequence is merged. Two ordered sequences can easily be merged into one ordered sequence.

Time complexity:


O ( n l o g 2 ( n ) ) O(nlog2(n))

Algorithm implementation:

C++

void merge_sort(int a[],int l,int r)
{
	if(l>=r) return; // The recursion ends when there is only one number in the sequence
	int mid=(l+r)>>1;	
	merge_sort(a,l,mid);merge_sort(a,mid+1,r);// Split the sequence in two to continue merge sort
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r) // Merge two ordered sequences into one ordered sequence
	{
		if(a[i]>a[j]) tmp[k++]=a[j++];
		else tmp[k++]=a[i++];
	}
	while(i<=mid) tmp[k++]=a[i++];// Insert the last number in the left sequence that does not participate in the comparison
	while(j<=r) tmp[k++]=a[j++];// Insert the last number in the right sequence that does not participate in the comparison
	for(i=l,k=0; i<=r; i++,k++) a[i]=tmp[k]; }Copy the code

Application of merge sort

One of the most common uses of merge sort is to find the number of reverse pairs in a sequence.

code

int cnt=0;
void merge_sort(int a[],int l,int r)
{
	if(l>=r) return; // The recursion ends when there is only one number in the sequence
	int mid=(l+r)>>1;	
	merge_sort(a,l,mid);merge_sort(a,mid+1,r);// Split the sequence in two to continue merge sort
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r) // Merge two ordered sequences into one ordered sequence
	{
		// If the sequence number on the left is larger than the sequence number on the right, it is an inverse pair.
		// And the last digit on the left is in reverse order with the current digit on the right
		if(a[i]>a[j]) {tmp[k++]=a[j++]; cnt+=(mid-i+1)} 
		else tmp[k++]=a[i++];
	}
	while(i<=mid) tmp[k++]=a[i++];// Insert the last number in the left sequence that does not participate in the comparison
	while(j<=r) tmp[k++]=a[j++];// Insert the last number in the right sequence that does not participate in the comparison
	for(i=l,k=0; i<=r; i++,k++) a[i]=tmp[k]; }Copy the code