merge.py

def merge(node):
    if node == NULL: return []
    left = merge(node.left_child)
    right = merge(node.left_child)
    if len(left) < len(right):
        swap(left, right)       #rightの方を小さくする
    res = combine(left, right)  #O(RlogL)
    return res.insert(node.val)

def combine(left, right): 
    if right == 空:return left
    return combein(left.insert(right[0]), right[1:])

#len(N)へのinsertはlog(N)でできるとする