@ the Author: Runsen

The essence of programming comes from algorithm, and the essence of algorithm comes from mathematics, programming is just to code mathematical problems. —- Runsen

Merge sort is an efficient sorting algorithm based on Merge operations. This algorithm is a very typical application of Divide and Conquer.

Divide and conquer algorithm

Divide-and-conquer method is to divide a complex problem into two or more identical or similar sub-problems, and then divide the sub-problems into smaller sub-problems until the sub-problems can be solved simply and directly. The solution of the original problem is the combination of the solutions of the sub-problems. (Baidu Encyclopedia)

When using divide-and-conquer strategy to solve, the time required depends on the number of subproblems after decomposition, the size of the subproblems and other factors, and dichotomy, because of its simple and uniform partition characteristics, is often used as an effective method, such as dichotomy retrieval.

The basic idea of divide-and-conquer algorithm is to decompose a scale N problem into K smaller sub-problems, which are independent from each other and have the same nature as the original problem. The solution of the original problem can be obtained by solving the subproblem. It is a divided objective completion program algorithm, simple problems can be solved by dichotomy.

The problems solved by divide-and-conquer generally have the following characteristics:

The original problem has the same pattern as the small problems decomposed into original problems. The small problems decomposed into original problems can be solved independently, and there is no correlation between the sub-problems.

With the termination condition of decomposition, when the problem is small enough, it can be solved between, and the solution of the decomposed sub-problem can be combined into the solution of the problem

Basic steps

  • Decompose, the problem to be solved into a number of smaller similar problems;
  • Solve, when the subproblem is divided enough small, with a simpler method to solve;
  • Merge, according to the requirements of the original problem, the solution of the sub-problem layer by layer merge to form the solution of the original problem.

Specific pseudocodes are as follows:

if(The problem is not separable): Returns the solutionelse: Draw a subproblem that contains half of the operands from the original problem1; Recursively call the divide-and-conquer procedure to get the solution1; Draw a subproblem that contains the other half of the operator from the original problem2; Recursively call the divide-and-conquer procedure to get the solution2; The solution1And the solution2Combine into a solution of the whole problem;Copy the code

Merge sort

Divide-and-conquer algorithm problem solving, one is binary search, one is merge sort.

Merge sort actually does two things:

Split: the core problem is to determine the split position, we can use the sum of left and right element index to divide 2, that is: mid = (left + right)/2, guide the split to the subsequence of only one element in the basic situation.

Merge: Merge is the heart of merge sort, the process of merging two sorted subsequences into a single sorted sequence. When there is only one element in the subsequence, the subsequence can be considered sorted, so our merge starts with two single-element subsequences.

When there are multiple elements in the subsequence, we need to get the current smallest element one by one to complete the whole sorting. In the process, we need a temporary area to store the sorted part.

What do you think about merging these two intervals into one ordered interval?

This is very simple, just compare two numbers of the first number, the smallest one is the first to take, then delete the number in the corresponding sequence. Then compare, if several columns are empty, it can directly take out the data of another column in turn.

"' @ Author: Runsen @ WeChat: RunsenLiu @ WeChat public number: the king of the Python @ CSDN: https://blog.csdn.net/weixin_44510615 @ making: https://github.com/MaoliRUNsen @ Date: 2020/12/21 "'
def merge(left, right) :  # merge two ordered arrays
    l, r = 0.0
    result = []
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result


def merge_sort(nums) :
    if len(nums) <= 1:
        return nums
    num = len(nums) >> 1  The # bit operation takes the middle
    left = merge_sort(nums[:num])
    right = merge_sort(nums[num:])
    return merge(left, right)
    
    
if __name__ == '__main__':
    nums = [54.26.93.17.77.31.44.55.20]
    print(merge_sort(nums))    

[17.20.26.31.44.54.55.77.93]
Copy the code

Merge sort has the worst, best, and average running time of O(NlogN), but it is not as widely used as quicksort. Why is this? Because it has a fatal “weakness”, that is, merge sort is not an in-place sort algorithm. It requires additional storage space of order N.

There is no genius. If you stand up to the time, the time will stand up to you. Pay attention to us, improve a little bit each day, and use fragmented time to learn.

GitHub, portal ~, GitHub, portal ~, GitHub, Portal ~