Problem
I have implemented a Merge sort in Python 3, and it works well. If anything needs to be improved, I would appreciate the criticism.
def merge_sort(nums):
if len(nums) == 1:
return
middle_index = len(nums) // 2
left_half = nums[:middle_index]
right_half = nums[middle_index:]
merge_sort(left_half)
merge_sort(right_half)
i = 0
j = 0
k = 0
while i<len(left_half) and j<len(right_half):
if left_half[i] < right_half[j]:
nums[k] = left_half[i]
i = i + 1
else:
nums[k] = right_half[j]
j = j + 1
k = k + 1
while i<len(left_half):
nums[k] = left_half[i]
k = k + 1
i = i + 1
if __name__ == "__main__":
nums = [-3,-2,-1,1,2,1,0,-1,-2,-3]
merge_sort(nums)
print(nums)
Solution
Everything I’m going to talk about is in the merge_sort function
General
i = 0
j = 0
k = 0
Can be defined as
i = j = k = 0
You should always leave spaces between operators as per PEP 8 rules
i<len(left_half) should be i < len(left_half)
Use x += y instead of x = x + y
In my opinion, I think using short and concise names such as mid or middle instead of middle_index would be better. If you don’t wish to, you can leave it as it!
Use type hints
Add docstrings
Bug
Your function only takes into account the left_half of the array, and ignores what’s left in the right_half
For example, if nums array was [3, 9, 0], The array would be [0, 3, 0]
This would happen as
merge_sort([3]) which won’t change the left_half
merge_sort([9, 0]) which would make the right_half as [0, 9]
Then,
left_half = [3]
right_half = [0, 9]
nums = [3, 9, 0]
i = 0
j = 0
k = 0
First, the else statement would be called as 3 > 0.
i = 0
j = 1
k = 1
nums = [0, 9, 0]
Next, the if statement would be called as 3 < 9
i = 1
j = 1
k = 2
nums = [0, 3, 0]
Now, the while loop will terminate as i = len(left_side)
Then, while i < len(left_side) would immediately terminate as i = len(left_side)
Did you notice? right_side still has one element 9 waiting to be traversed, but it never will be.
To fix that, add the following to the end of the function
while j < len(right_half):
nums[k] = right_half[j]
j += 1
k += 1
Improvement
Now, instead of using a while loop at all, you can just use a[k:] = left_half[i:] + right_half[j:] to replace both the loops! This is true because one half must be empty and the other half must have the length of n - k.
Performance
If you are using this function in real time with an array of a really large size, this won’t work efficiently.
len takes quite a bit of time. To make it even faster, use a parameter length which would be the length of the array
The final implementation of the function:
from typing import List, Any
def merge_sort(nums: List[Any], length: int) -> None:
""" Uses Merge Sort to sort an array """
# Base case
if length == 1:
return
mid = length // 2
left, right = mid, length - mid
left_half, right_half = nums[:mid], nums[mid:]
merge_sort(left_half, left)
merge_sort(right_half, right)
i = j = k = 0
while i < left and j < right:
if left_half[i] < right_half[j]:
nums[k] = left_half[i]
i += 1
else:
nums[k] = right_half[j]
j += 1
k += 1
nums[k:] = left_half[i:] + right_half[j:]
Note: Any in typing means any datatype is allowed. The function can sort any datatype that is comparable with another element of the same datatype.
For one you could change your code to non-recursive. Lists in python and recursion don’t mix well. In other words, what you did might work fine, but it could work a bit better.