Merge sort algorithm in python with code code example
Example 1: Merge Sort python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
return merge(left, right, arr.copy())
def merge(left, right, merged):
left_cursor, right_cursor = 0, 0
while left_cursor < len(left) and right_cursor < len(right):
if left[left_cursor] <= right[right_cursor]:
merged[left_cursor+right_cursor]=left[left_cursor]
left_cursor += 1
else:
merged[left_cursor + right_cursor] = right[right_cursor]
right_cursor += 1
for left_cursor in range(left_cursor, len(left)):
merged[left_cursor + right_cursor] = left[left_cursor]
for right_cursor in range(right_cursor, len(right)):
merged[left_cursor + right_cursor] = right[right_cursor]
return merged
Example 2: merge sort in python
def mergesort(list1):
if len(list1) >1 :
mid = len(list1)//2
left_list = list1[:mid]
right_list = list1[mid:]
mergesort(left_list)
mergesort(right_list)
i = 0
j = 0
k = 0
while i<len(left_list) and j<len(right_list):
if left_list[i]< right_list[j]:
list1[k] = left_list[i]
i+=1
k+=1
else:
list1[k] = right_list[j]
j+=1
k+=1
while i < len(left_list):
list1[k] = left_list[i]
i+=1
k+=1
while j < len(right_list):
list1[k] = right_list[j]
j+=1
k+=1
n = int(input("Enter how many element you want in the list : "))
list1 = [int(input()) for i in range(n)]
mergesort(list1)
print("sorted list : " + str(list1))