Why is this merge sort code a lot slower than python's default sort()?

Question

I took this merge sort example from a blog. I'm just starting to study merge sort and I wanted to check its speed compared to python's default sorting algorithm. With short random generated lists it's not very noticeable but with a big list, like one with 1,000,000 integers, it takes around 10 seconds, while python's default sorting algorithm doesn't even comes close to 1 second.

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)

Answer 1

Python is great for a lot of things but compared to many other languages it runs very slowly. The built-in functions in your typical Python distribution are written in C which is much faster than the equivalent Python code.