Recursive python merge doesn't work

Question

I am trying to implement a recursive merge sorting algorithm only with functions that return nothing, but I have difficulties with its operation. It seems that it splits the lists and sorts them correctly, but does not transfer these sorted lists to the next recursive call.

def merge(list1, list2): result = [] i = 0 j = 0 k = 0 while i < len(list1) and j < len(list2): if list1[i] < list2[j]: result.append(list1[i]) i+=1 else: result.append(list2[j]) j+=1 k+=1 while i < len(list1): result.append(list1[i]) i+=1 k+=1 while j < len(list2): result.append(list2[j]) j+=1 k+=1 print(result) def merge_sort(inplist): if int(len(inplist)) >1: mid = len(inplist)//2 left = inplist[0:mid] right = inplist[mid:] merge_sort(left) merge_sort(right) merge(left,right) test = [1,4,7,2,6,9,8,5,3,0] merge_sort(test) print(test) 

Answer 1

Indexing lists creates a new list ( left = inplist[0:mid] ). Since you do not seem to rewrite these new lists (after merging) in inplist, nothing will happen with inplist .

In fact, merge() combines the two lists, but then discards the result: you create result inside merge() , but you do nothing with it, so it will be discarded after the function exits.

I think you need to return result from merge() and assign it inplist ; something like (unverified):

 inplist[:] = merge(left, right)