HiveBrain v1.2.0
Get Started
← Back to all entries
snippetpythonMinorCanonical

Merge Sort Algorithm Python

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
sortpythonalgorithmmerge

Problem

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()

Solution

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 :-)

Code Snippets

if len(list) <= 1:
    return list

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

Context

StackExchange Code Review Q#148924, answer score: 6

Revisions (0)

No revisions yet.