“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Merge sort

Merge sort is a very typical application of divide-and-conquer. So the idea of merge sort is to recursively decompose an array and then merge an array and then decompose an array to a minimum and then merge two ordered arrays, and the basic idea is to compare the first number of the two arrays, and then take the smallest number, and then move the pointer back one. And then we compare, we know that an array is empty, and then we copy over the rest of the array

Basic implementation

1. There is a list of arrays like this. Split it in half into two arrays.2. Continue splitting until there is only one element per child, as shown below3. Merge after splitting. 56 and 26 are removed from the green box above.4. Merge the two green blocks, this time using the definition of the cursor, one refers to the Left most of the Left, one is the Right. The way you merge is you have a cursor for the left part, you have a cursor for the right part, and then you compare and transpose the two parts.5. After comparison, 17 is small, take it out, and then move Right back one.6. Then continue to compare the direction of Right is larger than 26, select 26, Left continues to move back one bit. After comparison, we find that Right is larger than Left, so we take out 54, and finally put Right behind to get the following ordered sequence.7. The right side continues in the same way to get two parts, and now there are only two parts for the whole sequence.8. Merge the data in the two green boxes in the same way as above. Again, the cursor Left, Right, Right, Right, Right. I get an ordered sequence

That’s the idea of a merge algorithm: you break up a group of elements until you have only one child, and then you merge them, sorting them by Left and Right.

So it’s going to be the same thing for an odd number of numbers, except when you split it up you get one more in the last group. And when you merge, you merge those two in the last gray box, and then you merge them with 44, and you merge them as you want.

Merge algorithm code implementation

''' Create by YO @Time: 2020/4/22 '''

# Two slashes have no decimal part when they are divided. Take down the whole
def merge_sort(alist) :
    Merge sort
    n=len(alist)
    if n<=1:
        return alist
    mid=n//2    # the median
    left_li=merge_sort(alist[:mid])
    #right A new list formed by merging sort
    right_li=merge_sort(alist[mid:])
    Merge two ordered subsequences into a new whole merge(left,right
    left_pointer,right_pointer=0.0
    result=[]

    while left_pointer<len(left_li) and right_pointer<len(right_li):
        if left_li[left_pointer]<right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer+=1   Move back one bit after moving
        else:
          result.append(right_li[right_pointer])
          right_pointer+=1
    result+=left_li[left_pointer:]
    result+=right_li[right_pointer:]
    return result


if __name__ == "__main__":
    li = [54.26.93.17.77.31.44.55.20]
    print(li)
    sorted_li=merge_sort(li)
    print(li)
    printOutput: [sorted_li54.26.93.17.77.31.44.55.20]
[54.26.93.17.77.31.44.55.20]
[17.20.26.31.44.54.55.77.93]
Copy the code

Time complexity

Optimal time complexity: O(nlogn)

Worst time complexity: O(nlogn)

Stability: stability