Merge Sort Algorithm Python

Question

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

Answer 1

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