def merge(arr1, arr2):
returned = []
while len(arr1) > 0 and len(arr2) > 0:
if arr1[0] >= arr2[0]:
returned.append(arr2[0])
arr2.pop(0)
else:
returned.append(arr1[0])
arr1.pop(0)
if len(arr1) > 0:
returned = returned + arr1
if len(arr2) > 0:
returned = returned + arr2
return returned
Above is the merge function. Below is the merge sort function.
def merge_sort(nums):
#print("Merge sorting following array:")
#print(nums)
if len(nums) == 1:
return nums
else:
middle = int(len(nums)/2)
first_half = nums[:middle]
#print("First half is:")
#print(first_half)
second_half = nums[middle:]
#print("Second half is:")
#print(second_half)
return merge(merge_sort(first_half), merge_sort(second_half))
It feels like something is off because I timed it using the time module, and it was about 4 times as fast as a bubble sort algorithm, on a list 10 numbers long. I think I may be overthinking the merge function, but cannot put my finger on what I am doing wrong.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…