Introduction to merge sort in JavaScript (code example)

This article brings you an introduction to merge sorting in JavaScript (code examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Merge sort (MERGE-SORT) is an effective sorting algorithm based on merge operations. The algorithm uses the divide and conquer method (pide andConquer) is a very typical application. Merge the already ordered subsequences to obtain a completely ordered sequence; that is, first make each subsequence orderly, and then make the subsequence segments orderly. If two ordered lists are merged into one ordered list, it is called a two-way merge.

Merge sort

Merge sort is a very stable sorting method. Its time complexity is NlogN whether it is average, best or worst.

Two steps of merge sort

1. Split first, then split until there is only one number

2. Split completed After that, start the recursive merge

Split process

As can be seen from the above figure, merge sort Will split an array into twos and stop splitting when there is only one number.
Then the splitting code is very simple, which is to get a pointer q pointing to the middle and split the array into two parts: (start, p) and (p, end).

• p represents the starting subscript of the array

• r represents the ending subscript of the array

    function pide(p, r){
        return Math.floor( (p + r) / 2 );
    }

Merge process

The merging process is as shown in the picture above

1. Traverse two sets of data

2. Compare the sizes

3. The smaller value is taken out and placed in the first position

For example:

• Assume that the data of array A is [2,5,1,3]

• After our splitting It will be (0,2),(2,4);

• We get two through A.slice(0,2) and A.slice(2,4)=> Arrays A1[2,5] and A2[1,3]

• Then we traverse the array [2,5,1,3], and for the first time we will get the comparison of both sides The small number is 1, the second time is 2, the third time is 3, and the fourth time is 5

    function merge(A, p, q, r){
        const A1 = A.slice(p, q);
        const A2 = A.slice(q, r);
        
        // 哨兵，往A1和A2里push一个最大值，比如防止A1里的数都比较小，导致第三次遍历某个数组里没有值
        
        A1.push(Number.MAX_SAFE_INTEGER);
        A2.push(Number.MAX_SAFE_INTEGER);
        // 循环做比较，每次取出较小的那个值
        for (let i = p, j = 0, k = 0; i <h3 id="Main-program">Main program</h3><p>The main program is to recursively repeat the above operation </p><pre class="brush:php;toolbar:false">    function merge_sort(A, p = 0, r) {
      r = r || A.length;
      if (r - p === 1) {
        return;
      }
      const q = pide(p, r);
      merge_sort(A, p, q);
      merge_sort(A, q, r);
      merge(A, p, q, r);
    
      return A;
    }

Complete code

    function pide(p, r) {
      return Math.floor((p + r) / 2);
    }
    
    function merge(A, p, q, r) {
      const A1 = A.slice(p, q);
      const A2 = A.slice(q, r);
      A1.push(Number.MAX_SAFE_INTEGER);
      A2.push(Number.MAX_SAFE_INTEGER);
    
      for (let i = p, j = 0, k = 0; i <p class="comments-box-content"></p>

The above is the detailed content of Introduction to merge sort in JavaScript (code example). For more information, please follow other related articles on the PHP Chinese website!