O(N*logN) sort algorithm: merge sort

Let’s start with a merge sort implementation code

function mergeSort(arr) {
     // Merge arrays already arranged on both sides
    function merge (left, mid, right) {
        let index1 = left
        let index2 = mid + 1
        let index = 0
        // Auxiliary array
        let help = Array(right - left + 1)
        while (index1 <= mid && index2 <= right) {
            if (arr[index1] <= arr[index2]) {
                help[index++] = arr[index1]
                index1++
            } else {
                help[index++] = arr[index2]
                index2++
            }
        }
        while (index1 <= mid) {
            help[index++] = arr[index1]
            index1++
        }
        while (index2 <= right) {
            help[index++] = arr[index2]
            index2++
        }
        index = 0
        for (; index < help.length; index++) {
            arr[left + index] = help[index]
        }
    }

    function process(left, right) {
        if (left === right) {
            return
        }
        // Prevent (left + right) /2 summation overflow
        const mid = left + ((right - left) >> 1)
        process(left, mid)
        process(mid + 1, right)
        merge(left, mid, right)
    }

    process(0, arr.length - 1)}Copy the code

conclusion

1. The time complexity of merge sort is O(n*logn) (recursive).
2. The spatial complexity of merge sort is: O(n) uses an auxiliary array
3. Why can merge sort do logN time, because you don’t waste every time you compare the size of the information, the ordered information is passed up to the recursive process

Merge sort extension problem:

Small and problem

The sum of the numbers to the left of each number smaller than the current number in an array is called the sum of the array.

Example [1,3,4,2,5] Solving process: 1 number less than 1 on the left: 0 3 number less than 3 on the left: 1 4 Number less than 4 on the left: 1,3 2 Number less than 2 on the left: 1 5 Number less than 5 on the left: 1,3,4,2 So the sum of small is 1+1+3+1+1+3+4+2=16Copy the code

The small sum problem can be considered in another way: finding the small sum of an array can be transformed into finding the number of occurrences of each element in the process of small sum accumulation, and then multiplying the current element by the number of occurrences to obtain the small sum. Assuming that the current element is A, the number of elements to the right of A that are larger than A is the number of occurrences of A in the summation process

Rewrite the merge sort code above. In the merge process, use the sorted left and right arrays to obtain the small sum of each item in the left array. (right-Index2 + 1) * arr[index1], that is, how many items in the right array (right-Index2 + 1) are larger than the current items in the left array (arr[index1]), to obtain the small sum of the items. It is worth noting that the merge procedure must sort the array. Without sorting, it is impossible to determine how many items in the right array are larger than arr[index1].

The code is as follows:

// merge sort small sum problem
function merge(arr, left, mid, right) {
    let index1 = left
    let index2 = mid + 1
    let sum = 0
    let help = []
    while (index1 <= mid && index2 <= right) {
        if (arr[index1] < arr[index2]) {
            help.push(arr[index1])
            sum += (right - index2 + 1) * arr[index1]
            index1++
        } else {
            // If the right is larger than the left, copy the right value first
            help.push(arr[index2])
            index2++
        }
    }
    while (index1 <= mid) {
        help.push(arr[index1])
        index1++
    }
    while (index2 <= right) {
        help.push(arr[index2])
        index2++
    }
    
    for (let i = 0; i < help.length; i++) {
        arr[left + i] = help[i]
    }
    return sum
}

function process (arr, left, right) {
    if (left === right) {
        return 0
    }
    const mid = left + ((right - left) >> 1)
    const leftSum = process(arr, left, mid)
    const rightSum = process(arr, mid + 1, right)
    return merge(arr, left, mid, right) + leftSum + rightSum
}

function getMinSum(arr) {
    return process(arr, 0, arr.length - 1)}Copy the code

Rewrite merge sort and solve small sum problems, the time complexity and space complexity of merge sort (O(n*logn) and O(n)).

Reverse the problem

Inversions: In a permutation, a logarithm is called an inversion if its front and back positions are in reverse order of magnitude, i.e. the number in front is larger than the number behind. The total number of inversions in a permutation is called the number of inversions of that permutation. ,

Merge (arr[index1]); merge (arr[index1]); merge (arr[index1]); merge (arr[index1]); merge (arr[index1]);

// merge sort to find the reverse order
function merge(arr, left, mid, right) {
    let index1 = left
    let index2 = mid + 1
    let sum = 0
    let help = []
    while (index1 <= mid && index2 <= right) {
        if (arr[index1] > arr[index2]) {
            help.push(arr[index1])
            sum += right - index2 + 1
            index1++
        } else {
            help.push(arr[index2])
            index2++
        }
    }
    while (index1 <= mid) {
        help.push(arr[index1])
        index1++
    }
    while (index2 <= right) {
        help.push(arr[index2])
        index2++
    }
    
    for (let i = 0; i < help.length; i++) {
        arr[left + i] = help[i]
    }
    return sum
}

function process (arr, left, right) {
    if (left === right) {
        return 0
    }
    const mid = left + ((right - left) >> 1)
    const leftSum = process(arr, left, mid)
    const rightSum = process(arr, mid + 1, right)
    return merge(arr, left, mid, right) + leftSum + rightSum
}

function getReverseSets(arr) {
    return process(arr, 0, arr.length - 1)}Copy the code

Rewrite merge sort and reverse order pair problem, time and space complexity is the same as merge sort (O(n*logn) and O(n)).

Article source, written on the basis of left god algorithm video content. Recommend her left god algorithm video, great, address: www.bilibili.com/video/BV13g…