# Merge sort and selection sort comparison taking too long

I have this python code that compares merge sort and selection sort, but it is taking "forever."

import time
import random

# Selection Sort Code #
def maxIndex(J):
return J.index(max(J))

def swap(LCopy, i, j):
temp = LCopy[i]
LCopy[i] = LCopy[j]
LCopy[j] = temp

# Implementation of selection sort
def selectionSort(L):
for i in range(len(L)-1, 1, -1):
j = maxIndex(L[0:i+1])
swap(L, i, j)

# Merge Sort Code #
# Assumes that L[first:mid+1] is sorted and also
# that L[mid: last+1] is sorted. Returns L with L[first: last+1] sorted

def merge(L, first, mid, last):

i = first # index into the first half
j = mid + 1 # index into the second half

tempList = []

# This loops goes on as long as BOTH i and j stay within their
# respective sorted blocks
while (i <= mid) and (j <= last):
if L[i] <= L[j]:
tempList.append(L[i])
#print L[i], "from the first block"
i += 1
else:
tempList.append(L[j])
#print L[j], "from the second block"
j += 1

# If i goes beyond the first block, there may be some elements
# in the second block that need to be copied into tempList.
# Similarly, if j goes beyond the second block, there may be some
# elements in the first block that need to be copied into tempList
if i == mid + 1:
tempList.extend(L[j:last+1])
#print L[j:last+1], "some elements in second block are left over"
elif j == last+1:
tempList.extend(L[i:mid+1])
#print L[i:mid+1], "some elements from first block are left over"

L[first:last+1] = tempList
#print tempList

# The merge sort function; sorts the sublist L[first:last+1]
def generalMergeSort(L, first, last):
# Base case: if first == last then it is already sorted

# Recursive case: L[first:last+1] has size 2 or more
if first < last:
# divide step
mid = (first + last)/2

# conquer step
generalMergeSort(L, first, mid)
generalMergeSort(L, mid+1, last)

# combine step
merge(L, first, mid, last)

# Wrapper function
def mergeSort(L):
generalMergeSort(L, 0, len(L)-1)

m = 10
n = 100000
n_increments = 9
baseList = [ random.randint(0,100) for r in range(n) ]

i = 0

while i < n_increments:
j = 0
sel_time = 0
mer_time = 0

while j < m:
# Do a Selection Sort #
x = time.clock()

selectionSort( baseList)

y = time.clock()

sel_time += ( y - x )

random.shuffle( baseList )

# Do a Merge Sort #

x = time.clock()

mergeSort( baseList )

y = time.clock()

mer_time += ( y - x )

random.shuffle( baseList )

j += 1
print "average select sort time for a list of", n, "size:", sel_time / m
print "average merge sort time for a list of", n, "size:", mer_time / m

j = 0
i += 1
n += 10000


## 1 Answer

The first reason that your code is slow is because you are implementing a selection sort which will be slow in any implementation. It has to scan through a large list looking for the values for each iteration. That's gonna be slow.

The second problem is that you freely create new lists. For example:

j = maxIndex(L[0:i+1])


The slice creates a new list and copies the elements in L into it. That works fine when you are dealing with small lists, but in the lists you are playing with here, thats gonna be a significant speed drain. For the most efficiency in cases like this you need to avoid creating new lists altogether and just move stuff between elements in the same list.

All in all, it isn't really much slower then I'd expect the algorithm you are implementing to be in Python. Nothing you are doing should produce pathologically bad performance. However, there is a reason why we use a sort implementation in C. If you are just interested in implementing algorithms for the learning experience, I suggest you use smaller lists. Thats a lot of data to sort with a bad algorithm.

• Winston is right, the maxIndex list slice will be perform a copy. Try islice from the itertools module: j=maxIndex(islice(L,0,i+1)). – Phil H May 3 '11 at 14:11
• @Phil H, I thought about suggesting that, but maxIndex passes over the list twice which makes use of an iterator problematic. – Winston Ewert May 3 '11 at 14:52
• Ah, I didn't read that function properly. In that case import itertools and do max(itertools.izip(islice(L,0,i+1),itertools.count())) - it is a pure iterator version with a single pass. – Phil H May 4 '11 at 7:55
• @Phil H, yeah, you can do that. But I didn't think the complexity worth introducing here. – Winston Ewert May 4 '11 at 14:45