九. sort 5 Largest Number

From the Example, we know
8 > 4 > 23 > 20 >1
Besides, 8 should be larger than 81.
Normal numerical comparison does not work anymore.

Thus, we need a thorough new method to compare.
Considering string comparison:
"4" > "23" > "20"
but, stop!
"8" < "81" which is opposite to our design,

Here comes an another method:
when we compare "8" and "81" =>
compare "8"+"81" and "81"+"8",
"881" is larger than "818"
Thus, "8" >“81” , done

class Solution:
    """
    @param nums: A list of non negative integers
    @return: A string
    """
    def largestNumber(self, nums):
        # write your code here
        def merge_sort(nums):
            if len(nums) < 2:
                return nums
                
            middle = len(nums)//2 
            left = merge_sort(nums[:middle])
            right = merge_sort(nums[middle:])
            
            i=0
            j=0
            sorted = []
            while j < len(right) and i < len(left):
                if (left[i] + right[j]) < (right[j] + left[i]):
                    sorted.append(right[j])
                    j+=1
                else:
                    sorted.append(left[i])
                    i+=1
            
            sorted.extend(left[i:])
            sorted.extend(right[j:])
            
            return sorted
        
        # turn int into string
        for i in range(0, len(nums)):
            nums[i] = str(nums[i])
        
        nums = merge_sort(nums)
        
        string = ""
        for i in nums:
            string +=i 
            
        if string[0] == "0":
            return "0"
        else:
            return string