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_halfmerge_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.
