Source

Sort this messy list / fusion.py

Full commit




class Fusion(object):
    """
    Fusion sort - O(nlog(n))
    """
    def __init__(self, l):
        self.unsorted_list = l

    def sort(self):
        l = self.unsorted_list
        def Tri_Fusion_interne(l):
            if len(l)<2:
                return l
            return self.merge(Tri_Fusion_interne(l[:len(l)//2]), Tri_Fusion_interne(l[len(l)//2:]))
        l[:] = Tri_Fusion_interne(l)

    def merge(self, l1, l2):
        """Merge two sorted lists."""
        l = []
        i = j =0
        n1=len(l1)
        n2=len(l2)
        while True:
            if i<n1 and j<n2:
                if l1[i]<l2[j]:
                    l.append(l1[i])
                    i+=1
                else:
                    l.append(l2[j])
                    j+=1
            elif i>=n1:
                l.extend(l2[j:])
                break
            else:
                l.extend(l1[i:])
                break
        return l