Merge sort implementation in python 3

Question

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)

Answer 1

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.

• Ray Butterworth: Why is mid better than middle or mid_point?
• Sriv: middle would work as well, but not middle_index or mid_point. I think the sizes are too big, but that's just my opinion!

Answer 2

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.