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)
Everything I’m going to talk about is in the
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)
x += y instead of
x = x + y
In my opinion, I think using short and concise names such as
middle instead of
middle_index would be better. If you don’t wish to, you can leave it as it!
Use type hints
Your function only takes into account the
left_half of the array, and ignores what’s left in the
For example, if
nums array was
[3, 9, 0], The array would be
[0, 3, 0]
This would happen as
merge_sort() which won’t change the
merge_sort([9, 0]) which would make the
left_half =  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
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.
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:]
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.