Everything I'm going to talk about is in themerge_sort function

General

i = 0j = 0k = 0

Can be defined as

i = j = k = 0

You should always leave spaces between operators as perPEP 8 rules

i<len(left_half) should bei < len(left_half)

Usex += y instead ofx = x + y

In my opinion, I think using short and concise names such asmid ormiddle instead ofmiddle_index would be better. If you don't wish to, you can leave it as it!

Usetype hints

Adddocstrings

Bug

Your function only takes into account theleft_half of the array, and ignores what's left in theright_half

For example, ifnums array was[3, 9, 0], The array would be[0, 3, 0]

This would happen as

merge_sort([3]) which won't change theleft_halfmerge_sort([9, 0]) which would make theright_half as[0, 9]

Then,

left_half = [3]right_half = [0, 9]nums = [3, 9, 0]i = 0j = 0k = 0First, the else statement would be called as 3 > 0.i = 0j = 1k = 1nums = [0, 9, 0]Next, the if statement would be called as 3 < 9i = 1j = 1k = 2nums = [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 element9 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 awhile loop at all, you can just usea[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 ofn - 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 parameterlength which would be the length of the array

The final implementation of the function:

from typing import List, Anydef 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 intyping means any datatype is allowed. The function can sort any datatype that is comparable with another element of the same datatype.

• \$\begingroup\$Why ismid better thanmiddle ormid_point?\$\endgroup\$

  Ray Butterworth

  – Ray Butterworth

  2019-11-27 15:51:00 +00:00

  CommentedNov 27, 2019 at 15:51
• \$\begingroup\$middle would work as well, but notmiddle_index ormid_point. I think the sizes are too big, but that's just my opinion!\$\endgroup\$

  Sriv

  – Sriv

  2019-11-27 15:53:19 +00:00

  CommentedNov 27, 2019 at 15:53

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.

• python
• python-3.x
• sorting
• mergesort