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