class Tree:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def size(self):
        size = 1
        size = size + self.left.size() if self.left is not None else size
        size = size + self.right.size() if self.right is not None else size
        return size

    def merge(self, tree):
        if tree is None:
            return self
        if self.data <= tree.data:
            if self.right is None:
                return Tree(data=self.data, left=tree, right=self.left)
            return Tree(data=self.data, left=tree.merge(self.right), right=self.left)
        if tree.right is None:
            return Tree(data=tree.data, left=Tree(data=self.data, left=self.left, right=self.right), right=tree.left)
        return Tree(data=tree.data, left=self.merge(tree.right), right=tree.left)

    def insert(self, data):
        self.__dict__ = self.merge(Tree(data, None, None)).__dict__.copy()

    def popgen(self):
        while self.left is not None or self.right is not None:
            yield self.data
            if self.left is not None:
                self.__dict__ = self.left.merge(self.right).__dict__.copy()
            else:
                self.__dict__ = self.right.__dict__
        yield self.data

    def to_list(self):
        return [x for x in self.popgen()]

    @classmethod
    def from_list(cls, lst):
        if not lst:
            raise ValueError("cannot build a tree from an empty list")
        tree = Tree(lst[0], None, None)
        if len(lst) > 1:
            for e in lst[1:]:
                tree.insert(e)
        return tree


def sort(lst):
    return Tree.from_list(lst).to_list()


if __name__ == '__main__':
    import random
    before = [random.randint(1, 100) for _ in range(10)]
    after = sort(before)
    print('unsorted: ', before)
    print('sorted:   ', after)
    print('native:   ', sorted(before))
    assert after == sorted(before)