Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Mergesort Algorithm - Python
def split_leftlist(list):
half = len(list) / 2
return list[:half]
def split_rightlist(list):
half = len(list) / 2
return list[half:]
def merge(left_list, right_list):
output_list = []
leftCounter = 0
rightCounter = 0
for count in range(len(left_list) + len(right_list)):
if rightCounter == len(right_list):
[output_list.append(each) for each in left_list[leftCounter: ]]
return output_list
elif leftCounter == len(left_list):
[output_list.append(each) for each in right_list[rightCounter: ]]
return output_list
if (left_list[leftCounter] <= right_list[rightCounter]):
output_list.append(left_list[leftCounter])
leftCounter += 1
elif (right_list[rightCounter] <= left_list[leftCounter]):
output_list.append(right_list[rightCounter])
rightCounter += 1
return output_list
def merge_sort(list):
if len(list) <= 1:
return list
left_list = split_leftlist(list) #Recursively split the left part of list
left_list = merge_sort(left_list)
right_list = split_rightlist(list)
right_list = merge_sort(right_list) #Recursively split the right part of list
return merge(left_list, right_list)
if __name__ == '__main__':
merge_sort([]) #Enter list goes here
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment