Method mergeSort

Array/KthLargestElementInAnArray.py:86–101

归并排序的基本思路是分治，把一个大问题分解成小问题。逐个解决小问题。 以长度的一半为基准点，将一个大列表分为两个小列表，一直分一直分，然后合并。 所以排序分为两步： 第一步是分解，第二步是合并。

(self, unsorted_list, key=None)

    def mergeSort(self, unsorted_list, key=None):
        """
            归并排序的基本思路是分治，把一个大问题分解成小问题。逐个解决小问题。
            以长度的一半为基准点，将一个大列表分为两个小列表，一直分一直分，然后合并。
            所以排序分为两步：
               第一步是分解，第二步是合并。
        """
        if len(unsorted_list) <= 1:
            return unsorted_list

        break_point = len(unsorted_list) // 2

        left = self.mergeSort(unsorted_list[:break_point])
        right = self.mergeSort(unsorted_list[break_point:])

        return self._decomposeAndMerge(left, right, key=key)

    def _decomposeAndMerge(self, unsorted_list_A, unsorted_list_B, key):
        sorted_list = []