JS implements merge sort

This article mainly introduces the JS implementation of merge sorting, which has certain reference value. Now I share it with everyone. Friends in need can refer to

Recursive memory stack analysis

I have never understood recursion deeply. The reason is that the recursive process is very abstract and I cannot clearly analyze the return process of the memory stack. By chance, I came across a blog post on recursion (I have to say that technical issues still require more google), and I suddenly became enlightened about the memory stack analysis of the recursive process. The analysis process is listed below:

// A C++ program to demonstrate working of recursion
#include<bits>
using namespace std;
void printFun(int test)
{
    if (test <p> The following figure is accurate. After the entire recursive process, if you encounter a single recursion problem in the future, you can use this method to analyze it (for multiple recursions, try to draw the two recursions in merge sort, but there is really no way to neatly type them out, so give up. ) </p>
<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn//upload/image/198/863/317/1530956481159780.jpg?x-oss-process=image/resize,p_40" class="lazy" title="1530956481159780.jpg" alt="JS implements merge sort"></p>
<p> Let’s get back to the point, let’s analyze the merge and sort. </p>
<h3 id="Merge-sort">Merge sort</h3>
<p>Merge sort adopts the idea of ​​​​divide and conquer. The first is "divide", which repeatedly divides an array into two small arrays until each array has only one element; secondly It is "curing". Starting from the smallest array, merge them in order of size until they are the size of the original array. The following is an illustration: </p>
<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn//upload/image/223/850/313/1530956488945859.png?x-oss-process=image/resize,p_40" class="lazy" title="1530956488945859.png" alt="JS implements merge sort"></p>
<p>Observe the process of "curing" , it can be seen that "curing" actually means merging already ordered arrays into a larger ordered array. So how to merge already sorted arrays into a larger sorted array? It's very simple. Create a temporary array C, compare A[0], B[0], put the smaller value into C[0], and then compare A[1] and B[0] (or A[0], B [1]), put the smaller value into C[1] until A and B have been traversed once. It can be seen that arrays A and B only need to be traversed once, so the time complexity of sorting two ordered arrays is O(n). </p>
<p>And "dividing" means dividing the original array into two parts one after another until there is only one element left in each array. The one-element array is naturally in order, so the process of "curing" can begin. </p>
<p>Time complexity analysis: The dividing process requires three steps: log8 = 3, and each step needs to traverse 8 elements once, so a total of 8 log8) instructions need to be run for 8 elements, then for n elements , the time complexity is O(nlogn). </p>
<p>The code uses two recursions, which is very abstract and difficult to understand. It took me a whole page of stack call diagrams to figure it out (it’s too messy so I won’t post it). You can try it. </p>
<pre class="brush:php;toolbar:false">// 融合两个有序数组，这里实际上是将数组 arr 分为两个数组
function mergeArray(arr, first, mid, last, temp) {
  let i = first; 
  let m = mid;
  let j = mid+1;
  let n = last;
  let k = 0;
  while(i<p>The above is the entire content of this article. I hope it will be helpful to everyone's study. For more related content, please pay attention to the PHP Chinese website! </p><p>Related recommendations: </p><p><a title="JS实现希尔排序" href="http://www.php.cn/js-tutorial-406221.html" target="_blank">JS implements Hill sorting</a><br></p><p><a title="Jquery添加loading过渡遮罩" href="http://www.php.cn/js-tutorial-406220.html" target="_blank">Jquery adds loading transition mask</a><br> </p>

The above is the detailed content of JS implements merge sort. For more information, please follow other related articles on the PHP Chinese website!