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.