为什么这个合并排序代码比python的默认排序()慢得多?[副本]

我从一个博客中获取了这个合并排序示例。我刚刚开始研究合并排序,我想检查它与python的默认排序算法相比的速度。对于随机生成的短列表,它不是很明显,但是对于一个大列表,比如一个有1000000个整数的列表,它需要大约10秒,而python的默认排序算法甚至不到1秒。

import random
import time


def mergeSort(alist):

 if len(alist)>1:
   mid = len(alist)//2
   lefthalf = alist[:mid]
   righthalf = alist[mid:]

   mergeSort(lefthalf)
   mergeSort(righthalf)

   i=0
   j=0
   k=0

   while i < len(lefthalf) and j < len(righthalf):
       if lefthalf[i] < righthalf[j]:
           alist[k]=lefthalf[i]
           i=i+1
       else:
           alist[k]=righthalf[j]
           j=j+1
       k=k+1

   while i < len(lefthalf):
       alist[k]=lefthalf[i]
       i=i+1
       k=k+1

   while j < len(righthalf):
       alist[k]=righthalf[j]
       j=j+1
       k=k+1


array = [random.randint(0,1000) for a in range(0,10000)]

#print "original random generated array:",array

start = time.clock()

sorted_array = mergeSort(array)

#print "\nSorted array: ", sorted_array

print "Time: ", str(time.clock() - start)

start1 = time.clock()

array = array.sort()

print "Time: ", str(time.clock() - start1)