2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Why is mid better than middle or mid_point? \$\endgroup\$ – Ray Butterworth Nov 27 '19 at 15:51
  • \$\begingroup\$ 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! \$\endgroup\$ – Sriv Nov 27 '19 at 15:53
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.