Natural Merge Sort
Add your data below:
Invalid user input
Try input with more numbers
Input Data
Sorted Data
Natural Merge Sort source code
def merge_routine(arr_a: List[int], arr_b: List[int]) -> List[int]:
res = []
while (len(arr_a) > 0 or len(arr_b) > 0):
if len(arr_a) == 0:
res.append(arr_b.pop(0))
elif len(arr_b) == 0:
res.append(arr_a.pop(0))
elif arr_a[0] < arr_b[0]:
res.append(arr_a.pop(0))
else:
res.append(arr_b.pop(0))
return res
def split_routine(arr: List[int]) -> List[List[int]]:
n = 0
res = []
sorted_sub_list = []
while n < len(arr)-1:
sorted_sub_list.append(arr[n])
if arr[n] > arr[n+1]:
res.append(sorted_sub_list)
sorted_sub_list = []
sorted_sub_list.append(arr[n])
res.append(sorted_sub_list)
return res
def sort(arr: List[int]) -> List[int]:
mergeStack = split_routine(arr)
while len(mergeStack) > 1:
arr_a = mergeStack.pop(0)
arr_b = mergeStack.pop(0)
mergeStack.append(merge_routine(arr_a, arr_b))
return mergeStack[0]