<p><a href="http://en.wikipedia.org/wiki/Merge_sort" rel="nofollow">Mergesort</a>易于实现。这是一个<a href="http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms" rel="nofollow">divide-and-conquer</a>算法,它将问题分解成更小的部分(对左半部分、右半部分进行排序,然后将它们组合起来)。在</p>
<pre><code>a = [[231,'cow',234334,2231319,323242],[3,'alien',2,2312,3212],[9,'box',234,2319,3242]]
def merge_sort(a):
# copy the original array so it's unaffected
b = a[:]
# if there are 2 or fewer elements, just compare and return in the right order
if len(b) < 2:
return b
elif len(b) == 2:
x,y = b
if x[1] <= y[1]:
return b
else:
return [y,x]
# if there are more than 2, break it to 2 sub-arrays and recursively sort both
else:
m = int(len(b)/2)
p1 = merge_sort(b[:m])
p2 = merge_sort(b[m:])
rs = []
# then combine them by repeatedly popping the smaller one
while len(p1) > 0 or len(p2) > 0:
if len(p1) == 0:
rs.append(p2.pop(0))
elif len(p2) == 0:
rs.append(p1.pop(0))
elif p1[0][1] <= p2[0][1]:
rs.append(p1.pop(0))
else:
rs.append(p2.pop(0))
return rs
print merge_sort(a)
</code></pre>