5
\$\begingroup\$

I started implementing algorithms to learn them in order to get better at programming. Here is a merge sort one and criticisms / optimizations are welcome.

import unittest
import random

def mergeSort(list):
    """Sorts a mutable list.

    Args:
      list: An unordered list

    Returns:
      The sorted list.
    """
    if len(list) > 1:
        middle = len(list) // 2
        left_sorted = mergeSort(list[:middle])
        right_sorted = mergeSort(list[middle:])
        i,j,k = 0, 0, 0
        merged_list = []
        while (k < len(list) and len(left_sorted) != i and len(right_sorted) != j):
            if left_sorted[i] < right_sorted[j]:
                merged_list.append(left_sorted[i])
                i+=1
            else:
                merged_list.append(right_sorted[j])
                j+=1
            k+=1
        # Handle remaining items in the list.
        if len(left_sorted) == i:
            merged_list += right_sorted[j:]
        elif len(right_sorted) == j:
            merged_list += left_sorted[i:]
        return merged_list
    else:
        return list

class test_mergeSort(unittest.TestCase):
    def test_mergeSort(self):
        random_list = [random.randrange(0, 1000) for _ in range(500)]
        self.assertEqual(mergeSort(random_list), sorted(random_list))

if __name__ == '__main__':
    unittest.main()
\$\endgroup\$
7
\$\begingroup\$

Reduce nesting

If you invert the condition if len(list) > 1: near the beginning and use an early return, you can reduce the level of nesting, making the code slightly easier to read:

if len(list) <= 1:
    return list

middle = len(list) // 2
left_sorted = mergeSort(list[:middle])
right_sorted = mergeSort(list[middle:])
# ...

Eliminate k

The variable k is unnecessary, as it will never reach len(list). You can delete it and all its uses.

Style

The implementation doesn't follow recommended conventions of naming and formatting. I suggest to read and follow PEP8.

The good

It's really great that you included unit tests, it made the review easier :-)

\$\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.