Merge Sort in Merge Sort

Merge sort = merge sort = merge sort = merge sort = merge sort

The Angle mark judgment is really disgusting, also as my friend said, it is easy to cross the line and not judge well.

References:

• Alrightchiu. Making. IO/SecondRound…

import copy

def merge1(x:list, y:list, debug=False):
    """ Using a stack """
    new_ = list()
    
    x_ = copy.copy(x)
    y_ = copy.copy(y)
    
    while x_ and y_:
        if x_[- 1] > y_[- 1]:
            new_.append(x_.pop(- 1))
        elif x_[- 1] == y_[- 1]:
            new_.append(x_.pop(- 1))
            y_.pop(- 1)
        else:
            new_.append(y_.pop(- 1))
    new_ = new_ + x_ + y_
    return new_

def merge2(x:list, y:list, debug=False):
    """ Simple use of corner markers """
    new_ = list() 
    x = copy.copy(x)
    y = copy.copy(y)
    
    idx_x = len(x) - 1
    idx_y = len(y) - 1
        
    while True:
        if debug:
            print(idx_x, idx_y)
        
        if idx_x >= 0 and idx_y >= 0:
            x_ = x[idx_x]
            y_ = y[idx_y]
        else:
            break
            
        if x_ > y_:
            new_.append(x_)
            idx_x -= 1
        elif x_ == y_:
            new_.append(x_)
            idx_x -= 1
            idx_y -= 1
        else:
            new_.append(y_)
            idx_y -= 1
    # The condition for break is that the corner marker is out of bounds, i.e., less than zero, i.e., two corner markers exist: one is -1, the other is a positive integer, and only the latter can be obtained by slice, i.e., tail
    tail = y[:idx_y+1] or x[:idx_x+1] 
    new_.extend(tail)
    return new_

a = [i for i in range(3.12.2)]
b = [i for i in range(1.30.10)]

m1 = merge1(a, b)
m2 = merge2(a, b)
assert m1 == m2, print("m1:",m1, "\nm2:",m2, "\na:",a, "\nb:",b)


Copy the code