[C language] merge sort

Catalog

Preface ：

Merge sort

1. Recursive version  

demonstration ：

Realization ：

2. Non recursive version

demonstration ：

Realization ：

---

Preface ：

        *(ゝω・*ฺ) hi~ Welcome to my article ~ Here I will introduce two implementation methods of merge sorting ： Recursion and non recursion .

        notes ： The following algorithms are in ascending order , Descending order only needs to be executed under the opposite conditions ~<*))>>=<

Merge sort

         Merge sort It's based on Merger An effective method of operation , The stability of the Sorting algorithm , The algorithm adopts Divide and conquer method （Divide and Conquer） A very typical application . The ordered subsequence Merge , Get completely ordered Sequence ; So let's make each subsequence in order , Then make the subsequence segments in order . If two ordered tables are merged into one ordered table , be called Merge two ways .

Merger ： Merging is actually dividing the whole into two parts , Then these two parts should be in order , Merge , Combine into a whole and order , If there is no order in these two sub parts, continue to divide , When it comes to monomer or nonexistence, it's orderly , Then step by step back .

Divide and conquer ：“ Divide and rule ”, It means to divide a complex problem into several small problems , And then divide up , It can be easily solved , Then the solution of the original problem is actually the combination of the solutions of these small problems . The application here is to divide it into small pieces for sorting , Finally, get together and arrange it once .

1. Recursive version  

demonstration ：

（ Let's say 2 6 3 0 1 4 5 This string of arrays to be sorted for demonstration ）

        1. Gradually divide into solvable problems ( Single or nonexistent is ordered )

         2. Merge from back to front

 

Realization ：

         After the above demonstration , It's not hard to see , The first is to put the whole The number to be sorted is gradually divided into small pieces , Then merge . This is obviously a little similar In the following order Algorithm , That is, you should deal with the left and right sides first , Then I'm merging .

         Based on this , The program is not difficult to implement ：

// Auxiliary merge sort recursive subfunction 
void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (begin >= end)
		return;// Recursion ends with a single or nonexistent interval 

	// Similar to the following sequence ：
	int middle = (begin + end) / 2;
	int begin1 = begin;
	int end1 = middle;
	int begin2 = middle + 1;
	int end2 = end;
	_MergeSort(a, tmp, begin1, end1);
	_MergeSort(a, tmp, begin2, end2);

	// At this time, I think  [begin1, end1]  and  [begin2, end2] The two intervals are orderly 
	// Merge algorithm 
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));// Memory manipulation function , You can copy the number of the entire array 

}

// Merge sort   Recursive version 
void MergeSort(int* a, int n)
{
	// First malloc An array 
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf(" Failed to request memory \n");
		exit(-1);
	}
	// For the first time  0  and  n - 1  Incoming closed interval 
	_MergeSort(a, tmp, 0, n - 1);
	free(tmp);
}

tmp Array ： When we merged , Need a medium to exchange numbers . If you operate on the original array , Will overwrite the original data , Cause data loss .

malloc: void *malloc( size_t size ); Request continuous space of specified bytes from heap memory .

memcpy：void* memcpy(void* dest, const void* src, size_t count); Copy the contents of a continuous space of specified bytes to dest.

_MergeSort： Subfunctions for recursion , Before merging , First, recurse both sides , Until you find satisfaction begin >= end End recursion when , Go back to the previous recursive function for the next operation , This will ensure that before merging , Both intervals are ordered .

2. Non recursive version

        If the recursive version has too much data , Too many iterations , Will cause stack overflow , If we can implement a non recursive version , Make it borrow heap memory to sort , Heap memory is much larger than stack memory , Don't worry about overflow .

         The implementation of non recursive version is a little special . I believe you also know the non recursive version of quicksort , That is achieved by using stack or queue data structure to store intervals . But is it applicable to the merge sort here .

        From the previous recursive version, we know , This merging sort is to merge the numbers of these two intervals in the form of ranking in front, that is, after ranking . If you use the stack to store these intervals , First, store 0 To n - 1, Then store 0 To middle,middle + 1 To end , Then you can't take it out directly , Because it is uncertain whether these two intervals are orderly , So you need to continue saving into the interval , Relative trouble .

        So let's think about it a little bit differently , Not all non recursive implementations need the help of data spaces like stacks , For example, the non recursive implementation of Fibonacci sequence , So can we implement it directly ？

demonstration ：

1. Belong to 2 Of n The number of permutations to the power ([0 7])

Be careful , In this demonstration , Each time, they are divided equally , Two, two . In order to achieve the accuracy of the code , Then we should distinguish No 2 Of n Odd and even times of power .

 2. Do not belong to 2 Of n Odd order of power ([0 6])

  We'll find out , For the first time, the interval 1 Conduct 2 Share 2 If you divide the shares 3 There is nothing to share , that 3 Keep it the same , Until there is 2 When assigned to this group, it can be carried out normally .

3. Do not belong to 2 Of n Even order of power ([0 9])

  The same can be found here , The first time is ok 2 Points of , But not later , So after two points in the back , The corresponding ones without groups also remain unchanged , Until there is a corresponding group .

Realization ：

        Separate directly , Then merge . This code is not easy to write , It mainly distinguishes the three situations in the above demonstration .

         We can define one gap Variable to determine the length of each interval , for the first time 1, The second time 2, third time 4, until <n The situation of , If the length of the array to be arranged is not 2 Of n To the power of , It is necessary to deal with it .

        There are two processing methods in the following program , For the other two cases in the above demonstration .

// Merge sort   Non recursive version 
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf(" Failed to apply for space \n");
		exit(-1);
	}
	// Whole exchange  - 1
//int gap = 1;
//while (gap < n)
//{
//	for (int i = 0; i < n; i += 2 * gap)// Cross two groups at a time 
//	{
//		int begin1 = i, end1 = i + gap - 1;              // [0, 0] [2, 2] [4, 4] [6, 6]
//		int begin2 = i + gap, end2 = i + 2 * gap - 1;    // [1, 1] [3, 3] [5, 5] [7, 7]

//		// Boundary adjustment ：begin1 Certainly not across the border , When end1 When you cross the border 
//		if (end1 >= n)
//		{
//			end1 = n - 1;
//			// Give Way 2 If the series does not exist 
//			begin2 = 1;
//			end2 = 0;
//		}
//		else if (begin2 >= n)
//		{
//			begin2 = 1;
//			end2 = 0;
//		}
//		else if (end2 >= n)
//		{
//			end2 = n - 1;
//		}
//		// Merger 
//		int j = begin1;
//		while (begin1 <= end1 && begin2 <= end2)
//		{
//			if (a[begin1] <= a[begin2])
//			{
//				tmp[j++] = a[begin1++];
//			}
//			else
//			{
//				tmp[j++] = a[begin2++];
//			}
//		}
//		while (begin1 <= end1)
//		{
//			tmp[j++] = a[begin1++];
//		}
//		while (begin2 <= end2)
//		{
//			tmp[j++] = a[begin2++];
//		}
//	}
//	memcpy(a, tmp, sizeof(int) * n);// Whole copy , that   No 2 To the power of n We need to adjust the boundary 
//	gap *= 2;
//}

	
	// Every exchange  - 2
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)// Cross two groups at a time 
		{
			int begin1 = i, end1 = i + gap - 1;             
			int begin2 = i + gap, end2 = i + 2 * gap - 1;    

			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
			// Merger 
			int j = begin1;
			int m = end2 - begin1 + 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * m);// Local copy ,end2 - begin1 + 1 
		}

		gap *= 2;
	}
	free(tmp);


}

gap：gap It is defined as the interval length of each division , The next time is the area where the two intervals merged last time , therefore gap Each cycle *2 that will do .

begin：begin1 and 2 Are the subscripts at the beginning of the two intervals . according to i The distinction between ,i The first is 0, So according to gap Area length ,begin1 Naturally i,begin2 It has crossed an area , So it is i+gap

end：end1 and 2 Is the subscript at the end of two regions ,end1 Is the last subscript of the first region , Naturally, it is the beginning of the second region minus one , So it is i+gap - 1.end2 Is the last subscript of the second region , So naturally, it is the beginning of the third region minus one , namely i+gap*2-1.

For two special cases , There are two ways to deal with it , In fact, it is a kind of , Just for memcpy It makes a difference whether it is copied section by section or as a whole . One is to skip the next step without processing , One is to deal with , Optimize the boundary .