Saturday, November 9, 2013

Merge Sort

# -*- coding:utf-8 -*-
#!/usr/bin/python2
"""
=====================================================
Merge Sort
Shijie Xu <xushijie520@gmail.com>
Created on Mon, Nov 9, 2013
=====================================================
"""
L = [7, 10, 5, 8, 1, 3, 2, 4, 6, 9]
def merge(x, y):
    L = []
    while (len(x) > 0) and (len(y) > 0):
        if x[0] < y[0]:
            L.append(x[0])
            x.pop(0)
        else:
            L.append(y[0])
            y.pop(0)
    L += x if len(x) > 0 else y
    return L

def msort(m):
    if len(m) < 2:
        return m
    else:
        mid = len(m) // 2
        L1 = msort(m[:mid])
        L2 = msort(m[mid:])
        l_result = merge(L1, L2)
        return l_result

reuslt = msort(L)
print reuslt

No comments:

Post a Comment