'''
Created on Sep 22, 2015
@author: wangbin
'''
#O(N*lgN)
def merge(a, p, q, r):
L = a[p: q + 1]
L.append(2 ** 31)
R = a[q + 1: r + 1]
R.append(2 ** 31)
i = 0
j = 0
for k in range(p, r + 1):
# print("%d %d %d %d %d" % (p, q, r, i, j))
if L[i] < R[j]:
a[k] = L[i]
i += 1
else:
a[k] = R[j]
j += 1
def mergeSort(a, p, r):
if p < r :
q = int((p + r) / 2)
mergeSort(a, p, q)
mergeSort(a, q + 1, r)
merge(a, p, q, r)
if __name__ == "__main__":
a = [2, 4, 1, 6, 3, 9, 10, 5, 7, 8, 3, 1]
mergeSort(a, 0, len(a) - 1)
print(a)