codepad

Language:

def merge_sort(A):
    """Merge sort a list using the divide-and-conquer method."""
    
    # we will need these two functions to divide a list
    from math import floor, ceil
    
    def divide(L):
        """Divide list L into roughly two equal halves and conquer each half."""
        
        # a list of length 0 or 1 is a sorted list, we will return it and start
        # popping off call frames, ie: conquering divided lists
        if len(L) < 2:
            return L
        
        # split the list in two
        A = L[0:int(floor(len(L)/2))]
        B = L[int(ceil(len(L)/2)):]
        
        print "divide", A, B
        
        # recursively divide, and merge their conquered results
        return conquer(divide(A), divide(B))
    
    def conquer(A, B):
        """Take two sorted lists, A and B, and merge them together."""
        C = []
        
        # go through the elements of each list and add them to the final list
        # C. This will only end up iterating as far as min(len(A), len(B)) and
        # so
        i = 0
        j = 0
        min_len = min(len(A), len(B))
        while (i < min_len) and (j < min_len):
            if A[i] < B[j]:
                C.append(A[i])
                i = i+1
            else:
                C.append(B[j])
                j = j+1
        
        # we've merged up to the min length, lets add the rest of the other
        # list in now, because it is already sorted.
        C.extend((i < len(A) and A[i:]) or B[j:])
        
        # the sublist is now sorted
        print "conquer", C
        return C
        
    return divide(list(A))

# test the merge sort
if __name__ == "__main__":
    ls = [5, 8, 3, 1, 2, 99, 14, 7]
    print merge_sort(ls)

Private [?]

Run code