#coding: UTF-8
import sys
class Solustion:
    def mergySort(self,list):
        if len(list) <= 1:
            return list
        mid = len(list)/2
        left = self.mergySort(list[:mid])
        right = self.mergySort(list[mid:])
        return self.mergy(left,right)
    def mergy(self,left,right):
        res = []
        while len(left) and len(right):
            if left[0]<=right[0]:
                res.append(left[0])
                left.pop(0)
            elif left[0]>right[0]:
                res.append(right[0])
                right.pop(0)
        res += left
        res += right
        return res