Wednesday, May 13, 2009

Implementation of sort algorithms in python (part II – merge sort)

I am continuing my quest to implement all sort algorithms in python programming language. In this post I have implemented merge sort algorithm. Enjoy! (Previous post is available here).
"""
Merge sorting algorithms implemented in python
GUID of this code sniped: 83d44e30-e7b4-439e-b9eb-7dae165bf1af 
Author: Darius Kucinskas (c) 2008-2009
Email: d[dot]kucinskas[eta]gmail[dot]com
Blog: http://blog-of-darius.blogspot.com/
License: GPL
"""
def merge(left, right):
    r = []
    
    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            r.append(left[0])
            left = left[1:]
        else:
            r.append(right[0])
            right = right[1:]
            
    if len(left) > 0:
        r.extend(left)

    if len(right) > 0:
        r.extend(right)
    
    return r
    
def merge_sort(l):
    size = len(l)
    if size <= 1:
        return l

    middle = (size/2) - 1
    
    left = l[:middle+1]
    right = l[middle+1:]

    left = merge_sort(left)
    right = merge_sort(right)

    r = []
    if left[len(left) - 1] > right[0]:
        r = merge(left, right)
    else:
        r = merge(right, left)

    return r

if (__name__ == "__main__"):
    l = [i for i in range(10000)]
    print "sorted list"
    print l

    random.shuffle(l)
    print "unsorted original list"
    print l

    t1 = time.clock()
    lsorted = merge_sort(l)
    t2 = time.clock()
    print "soted list:"
    print lsorted
    print "merge sort time: %f " % (t2 - t1,)