JS implementation of graphic merging and sorting process [source code attached]

Introduce

         Merge sort is a sort of sort worth learning in many sorts , In terms of time complexity, he can guarantee that O(nlogn) It's a stable sort , And his sorting using divide and conquer idea is very good , Here we can first introduce the general idea of merging and sorting .

Ideas

        The idea of merging and sorting is called divide and conquer , in other words , Decomposition before treatment . So merge sort first uses the idea of similar bisection to split the array layer by layer , The splitting process does not perform sorting . When it is decomposed to the minimum cell, the adjacent elements in the minimum cell are compared and summarized into a new array layer by layer , Finally, merge to the original array . In other words, merge sort needs to create temporary extra space to handle each data merge during the sorting process . His idea is to split it into the smallest unit first , Finally, the smallest cells are merged into n An ordered array , Then merge the two ordered arrays into a new ordered array .

The illustration

        Let's first introduce the process of splitting in the idea of partition and rule with a diagram . Because the idea is similar to binary search , So the first step is to find the middle value in the array , Because there may be odd and even differences, our middle position is not an absolute median , So here we use Math.floor((0,arr.length-1)/2) To determine the intermediate value , This time, we still take the last array data as an example

let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]

Here we deliberately use the odd length array as an example to see the decomposition process . Please refer to the following figure. ：

  The above is the dichotomy based on the intermediate value we just described , Further decomposition to a single element , We will exchange and merge the grouped individual elements layer by layer from bottom to top .

First, we will sort and exchange the elements in the same group at the lowest level and return to the penultimate layer , Then continue to merge up layer by layer, as shown in the following figure .

  The above figure has vividly described the merging idea of merging and sorting , We can see from the picture that except for the bottom node exchange , When bubbling up layer by layer, we can also see that these are two ordered arrays for sorting , So we can quickly build a new ordered array , Until the last merge, only two arrays are left to merge .

Code implementation

//  Define an array 
let arr = [13,2,7,21,8,65,2,0,1,9,14,7,63]
//  Output the original array 
console.log(arr)
/**
 *  The actual function of sorting 
 * @param {Object} arr  Target array 
 * @param {Object} left  The starting position 
 * @param {Object} right  Termination position 
 * @param {Object} temp  Temporary array 
 */
function sortMerge(arr,left,right,temp){
	// If the start position is smaller than the end position, the sorting logic is enabled 
	if(left<right){
		// Determine the median , Divide the array into two parts 
		let mid = Math.floor((left+right)/2)		
		// Recursively perform the decomposition of the left part 
		sortMerge(arr,left,mid,temp)
		// Recursively perform the decomposition of the right part 
		sortMerge(arr,mid+1,right,temp)
		// After decomposition, merge from the last level of recursion 
		// Define the starting point of the array comparison in the left part 
		let l = left
		// Define the starting point of the right array comparison 
		let r = mid+1
		// Define the starting point of the temporary array 
		let k = 0
		// When either the left array or the right array is not finished , Because decomposition may 
		// The left and right arrays are different in length 
		while(l<=mid&&r<=right){
			// Determine which element to put in the array first , Move the temporary array pointer 
			// And move the pointer of the array to be compared 
			if(arr[l]>=arr[r]){
				temp[k] = arr[r]
				r++
				k++
			}else{
				temp[k] = arr[l]
				l++
				k++
			}
		}
		// When the above loop jumps out, it means that at least one array has come to the end 
		// Compare whether the left array has reached the destination , If not, continue to value the temporary array 
		while(l<=mid){
			temp[k] = arr[l]
			l++
			k++
		}
		// Compare whether the right array has reached the end point. If not, continue to value the temporary array 
		while(r<=right){
			temp[k] = arr[r]
			r++
			k++
		}
		// Remake temporary array pointer 
		k = 0
		// Put the sorting result of the temporary array into the original array from the merged length range 
		while(left<=right){
			arr[left] = temp[k]
			left++
			k++ 
		}
		// Output the sorting result 
		console.log(arr)
	}
}
/**
 *  A function that performs sorting 
 * @param {Object} arr  Array 
 */
function sort(arr){
	let left = 0
	let right = arr.length-1
	let temp = []
	sortMerge(arr,left,right,temp)
}
sort(arr)

The above is the actual js The code implementation of sorting logic , Here we can output the results of each sorting process to have a deeper understanding of the picture process .

summary

         In this issue, we learn the idea of merging and sorting , Here we find that it overlaps with the ideas of heap sort and quick sort , Both use the idea of data structure , But the implementation is different , For the commonly used algorithms in programming, as long as we understand the idea of diagrams, the implementation for developers is just the difficulty of reading pictures and writing words , So don't complicate them or recite them . This sharing is over , I look forward to meeting you in the next sharing .