My mergesort implementation currently takes a very long time, for a list with 1 million elements it takes over 130 seconds to get the list sorted.
Could someone kindly have a look at my code and suggest what could I do to improve it?
Is there anything particular in my code that is taking significantly long?
Code
def splitlist(L): #splits the list to a list of individual listed elements (e.g. [1,2] to [[1],[2]])
envelop = lambda x: [x]
return(list(map(envelop,L)))
def merge(L_1,L_2): #merges two (already sorted) lists to one sorted list
N = []
while len(L_1) > 0 and len(L_2) > 0:
if L_1[0] > L_2[0]:
N += [L_2.pop(0)]
else:
N += [L_1.pop(0)]
if len(L_1) == 0:
N += L_2
else:
N += L_1
return(N)
#performs one round of pairwise merges (e.g. [[2],[1],[4],[3]] to [[1,2],[3,4]]), or [[5,10],[1,8],[2,3]] to [[1,2,3,5,8,10]])
def mergelist(L):
N = []
if len(L) % 2 == 0:
for i in range(0,len(L)//2):
N += [merge(L[2*i],L[2*i + 1])]
else:
for i in range(0,len(L)//2 - 1):
N += [merge(L[2*i],L[2*i + 1])]
N += [merge(merge(L[-3],L[-2]),L[-1])]
return(N)
def mergesort(L): #recursively performs mergelist until there is only 1 sorted list remaining
L = splitlist(L)
while len(L) > 1:
L = mergelist(L)
return(L[0])
Here is my code for generating the million elements:
rlist = random.sample(range(0,2000000),1000000)
numpy.array
instead of lists, those are better optimized. \$\endgroup\$