# -*- coding: utf-8 -*-
"""
Created on Wed May 14 16:14:50 2014

@author: lifeix
"""

def merge(a, start, mid, end):
    if start == end:
        return a
    if mid == 0:
        return a
    
    temp1 = a[start:mid]
    m1 = len(temp1)/2
    print temp1,‘----‘,m1
    newtemp1 = merge(temp1,0,m1,len(temp1))    
    temp2 = a[mid:end]
    
    m2 = len(temp2)/2
    
    newtemp2 = merge(temp2,0,m2,len(temp2))
    #通过插入排序合并被排序的两个子数组
    for i in range(len(newtemp1)):
        t = newtemp1[i]
        for j in range(len(newtemp2)):
            if t > newtemp2[j]:
                temp = t
                
                t = newtemp2[j]
            
                newtemp2[j] = temp
        newtemp1[i] = t
                
    return newtemp1+newtemp2

a = [1,5,3,78,4,56,21]
mid = len(a)/2
merge(a,0,mid, len(a))