分而治之：归并排序（续） ·问题：如何对各组排序？ 似乎可以利用递归：对每一组再次应用分而治之 的归并排序因为满足递归的前提条件： 一奠基情形：组中只有一个数据时无需递归； 一每次分组都使列表变小，最终会到达奠基情形 def mergesort (nums): n len(nums) if n 1: m=n/2 nums1,nums2 nums [m],nums [m: mergesort (nums1) mergeSort(nums2) merge (nums1,nums2,nums)分而治之:归并排序(续) • 问题:如何对各组排序? • 似乎可以利用递归:对每一组再次应用分而治之 的归并排序.因为满足递归的前提条件: – 奠基情形:组中只有一个数据时无需递归; – 每次分组都使列表变小,最终会到达奠基情形. def mergeSort(nums): n = len(nums) if n > 1: m = n / 2 nums1, nums2 = nums[:m], nums[m:] mergeSort(nums1) mergeSort(nums2) merge(nums1, nums2, nums)