This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging

Abstract

Merge sort is to split the sequence down into the smallest sequence (only two elements), and then sort from there, and then merge up into new sequences and sorts until it is merged into one sequence (in which case, the sequence is ordered).

Code implementation with recursive thinking processing, merge sort in time complexity than the first three kinds of advantages, specific can be used what kind of scene, temporarily did not think of, first to learn logic, increase insight.

logic

Merge sort is somewhat space-for-time, so the code implementation creates a temporary sequence. The specific logic is as follows:

  1. The sequence is divided evenly into two subsequences until each subsequence has only one element
  2. Continue to merge subsequences into ordered sequences until it becomes a sequence

implementation

Creates a temporary sequence that is half the length of the sequence for sequence merging.


	leftArray = (E[])new Comparable[array.length >> 1];
	
	sort(0, array.length);
Copy the code

Here’s the idea of recursion, breaking the sequence down to the smallest unit (only two elements). This recursion is a little bit harder to understand and the order in which it’s executed, but I’m going to make a little bit of a point here.

Recursive idea: when there is recursive code in the method, when the code is executed to the recursive method, the recursive method will be directly executed, until the end of the condition is met, will return layer by layer, and execute the code block after the recursive method.

There must be a condition that terminates the recursion, otherwise the recursion will end in an infinite loop.

Basically, you split the sequence recursively until you have less than or equal to two elements, then you go back up and merge the sequence with the merge method.

/* * Merge sort of data from [begin, end) * */
private void sort(int begin, int end) {
	if (end - begin < 2) return;
		
	int mid = (begin + end) >> 1;
	sort(begin, mid);
	sort(mid, end);
	merge(begin, mid, end);
}
Copy the code

There are two interesting things to do with merge sort:

  1. When you look at the while loop, why just judgeli<leWithout judging the right? Because the left side is a temporary sequence, you want to put the ordered elements in one after the otherarray, so we only need to consider the two extreme cases, the temporary sequence is smaller than the right side, then the right side sequence does not need to move after the temporary sequence elements are put in. The right side of the sequence is smaller than the temporary sequence, so we’re going to put the right side of the sequence forward, and then we’re not going to end the while loop, we’re going to keep putting the temporary sequence in, until we’re done with the temporary sequence.
  2. Here to seearrayThere’s always one, so part of the sequence is also in orderarrayTo do that, usebeginandendTo get the true position in the sequence. The advantage of doing this is that you don’t have to create extra space to do it.

One of the questions when sorting is, isn’t there a left side or a right side that’s not ordered?

The answer is definitely no. Because from a recursion point of view, when you do a merge sort, you go up, and when you do a merge sort at the top, it’s already sorted down.


private void merge(int begin, int mid, int end) {
	int li = 0, le = mid - begin;
	int ri = mid, re = end;
	int ai = begin;
		
	// Back up the left array
	for (int i = li; i < le; i++) {
		leftArray[i] = array[begin + i];
	}
		
	// If there is no end to the left
	while (li < le) {
		if (ri < re && cmp(array[ri], leftArray[li]) < 0) { // Add stability
			array[ai++] = array[ri++];
		} else{ array[ai++] = leftArray[li++]; }}}Copy the code

The idea of merging in code, which can be used in the scenario of merging two ordered sequences, is a great idea.

Time and space complexity

  • Worst, average time complexity: O(nlogn)
  • Best time complexity: O(nlogn)
  • Space complexity: O(n)
  • It’s a stable order