Merge sort definition and principle:

Merge-sort is an application of MERGE SORTmergeThe idea of realizing the sorting method, the algorithm adopts the classicalDivide and conquerDivide-and-conquer strategies will make problemspointsDivide into small problems and solve them recursivelyTo treat (conquer)“And” patch “the answers together, i.e. divide and conquer.

The data structure of binary merging is very similar to binary tree structure and is generally carried out recursively.

Resolution:

Step 1: Divide

Decompose the array into a minimum unit, and take the middle element as the decomposition point each time, as shown in the figure:

Each layer of cutting is in the cut array after the result of continuous cutting, using recursive decomposition, when the cut array still has one element, out of the recursion

const sliceArray = function(arr) {
    if (arr.length < 2) {
        return arr
    }
   let mid = Math.floor(arr.length  / 2)
   let left = sliceArray(arr.slice(0, mid))
   let right = sliceArray(arr.slice(mid, arr.length))  
}
Copy the code

After cutting, there is a combined operation, that is, treatment.

Step 2: Cure

This is basically the operation of merging arrays, sorting them simultaneously. As shown in figure:

Main idea of merge operation:

Set double space, create a new array pointer to the beginning of the array, respectively, in order to compare the size of a push into the new array, and control the movement of the pointer, when the cursor moves to, finally can splice array elements behind the unfinished (cut after the array is also after the merger, that is to say the array itself is sort of, when one side pointer after the walk, The other side can be spliced directly after the result.)

Illustration:

Merge operation code:

const mergin = function (l1, l2) {
    let temp = []
    while(l1.length && l2.length) {
        const n1 = l1.shift()
        const n2 = l2.shift()
        if (n1 > n2) {
            temp.push(n2)
            l1.unshift(n1)
        } else {
            temp.push(n1)
            l2.unshift(n2)
        }
    }
    return [...temp, ...l1, ...l2]
}
Copy the code

Complete code:

/**
 * @param {number[]} nums
 * @return {number[]}
 */

const mergin = function (l1, l2) {
    let temp = []
    while(l1.length && l2.length) {
        const n1 = l1.shift()
        const n2 = l2.shift()
        if (n1 > n2) {
            temp.push(n2)
            l1.unshift(n1)
        } else {
            temp.push(n1)
            l2.unshift(n2)
        }
    }
    return [...temp, ...l1, ...l2]
}

const sliceArray = function(arr) {
    if (arr.length < 2) {
        return arr
    }
   let mid = Math.floor(arr.length  / 2)
   let left = sliceArray(arr.slice(0, mid))
   let right = sliceArray(arr.slice(mid, arr.length))
  return mergin(left, right)
   
}

var sortArray = function(nums) {
   return sliceArray(nums)
};
Copy the code