Reputation: 37
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.
Upvotes: 0
Views: 68
Reputation: 145307
Your implementation is mostly functional, but it has some shortcomings:
arr1
and arr2
.arr2
then from arr1
.Here is an alternative you can time and compare:
def merge(arr1, arr2):
result = []
i = 0
j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i = i + 1
else:
result.append(arr2[j])
j = j + 1
return result + arr1[i:] + arr2[j:]
def merge_sort(nums):
if len(nums) <= 1:
return nums
else:
middle = len(nums) >> 1
first_half = nums[:middle]
second_half = nums[middle:]
return merge(merge_sort(first_half), merge_sort(second_half))
Upvotes: 2