Algorithms-Reference

Sorting

Merge Sort

class MergeSort(object):
    def merge(self, a1, a2):
        i,j=0,0
        res=[]
        while i<len(a1) and j<len(a2):
            if a1[i]>a2[j]:
                res.append(a2[j])
                j+=1
            else:
                res.append(a1[i])
                i+=1
        if i<len(a1):
            res+=a1[i:]
        if j<len(a2):
            res+=a2[j:]
        return res

    def split(self, array):
        if len(array)==1:
            return [array[0]]
        if len(array)==2:
            return self.merge([array[0]],[array[1]])
        else:
            lo=0
            hi=len(array)-1
            mid=int((lo+hi)/2)
            return self.merge(self.split(array[:mid]),self.split(array[mid:]))


MergeSort().split([1,2,3,9,8,7,6,5,4,3,2,1])

[1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9]