Reputation: 23
I'm trying to implement mergeSort on my own, but the order of the returned list is still not correct. I must be missing something (especially by the merge step), could someone pls help me what it is?
Here is my code:
def merge(left_half, right_half):
"""
Merge 2 sorted lists.
:param left_half: sorted list C
:param right_half: sorted list D
:return: sorted list B
"""
i = 0
j = 0
B = []
for item in range(len(left_half) + len(right_half)):
while i < len(left_half) and j < len(right_half):
if left_half[i] <= right_half[j]:
B.insert(item, left_half[i])
i += 1
else:
B.insert(item, right_half[j])
j += 1
B += left_half[i:]
B += right_half[j:]
print("result: ", B)
return B
def mergeSort(A):
"""
Input: list A of n distinct integers.
Output: list with the same integers, sorted from smallest to largest.
:return: Output
"""
# base case
if len(A) < 2:
return A
# divide the list into two
mid = len(A) // 2
print(mid)
left = A[:mid] # recursively sort first half of A
right = A[mid:] # recursively sort second half of A
x = mergeSort(left)
y = mergeSort(right)
return merge(x, y)
print(mergeSort([1, 3, 2, 4, 6, 5]))
Before the last merge I receive the two lists [1, 2, 3] and [4, 5, 6] correctly, but my final result is [3, 2, 1, 4, 5, 6].
Upvotes: 2
Views: 86
Reputation: 22324
In the first iteration of your for-loop, you entirely traverse one of the lists, but always insert
at index 0
.
You do not want to insert
an element, you always want to append
it. This then makes the for-loop unecessary.
Here is a fixed version of your code:
def merge(left_half, right_half):
"""
Merge 2 sorted arrays.
:param left_half: sorted array C
:param right_half: sorted array D
:return: sorted array B
"""
i = 0
j = 0
B = []
while i < len(left_half) and j < len(right_half):
if left_half[i] <= right_half[j]:
B.append(left_half[i])
i += 1
else:
B.append(right_half[j])
j += 1
B += left_half[i:]
B += right_half[j:]
print("result: ", B)
return B
merge([1, 2, 3], [4, 5, 6])
# result: [1, 2, 3, 4, 5, 6]
Upvotes: 1