南京大学：《并行处理技术——分布式与并行计算 Distributed and Parallel computing（并行计算——结构、算法、编程）》课程教学资源（课件讲稿）第六章 并行算法的基本设计技术

第六章并行算法的基本设计技术 6.1划分设计技术 6.2分治设计技术 63平衡树设计技术 6.4倍增设计技术 6.5流水线设计技术

第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术

6.1划分设计技术 6.1.1均匀划分技术 6.1,2方根划分技术 6.1.3对数划分技术 6.1,4功能划分技术

6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术

归并排序(Merge Sort) A merge sort works as follows: If the list is of length o or 1,then it is already sorted. Otherwise: Divide the unsorted list into two sublists of about half the size. 米 Sort each sublist recursively by re-applying the merge sort. Merge the two sublists back into one sorted list. 2011/10/25

 A merge sort works as follows:  If the list is of length 0 or 1, then it is already sorted. Otherwise:  Divide the unsorted list into two sublists of about half the size.  Sort each sublist recursively by re‐applying the merge sort.  Merge the two sublists back into one sorted list. 归并排序（Merge Sort） 5 2011/10/25

归并排序(Merge Sort.) 米 Merge sort incorporates two main ideas to improve its runtime: A small list will take fewer steps to sort than a large list. Fewer steps are required to construct a sorted list from two sorted lists than from two unsorted lists.For example,you only have to traverse each list once if they're already sorted. 6 2011/10/25

 Merge sort incorporates two main ideas to improve its runtime:  A small list will take fewer steps to sort than a large list.  Fewer steps are required to construct a sorted list from two sorted lists than from two unsorted lists. For example, you only have to traverse each list once if they're already sorted. 归并排序（Merge Sort） 6 2011/10/25

归并排序示例 2011/10/25

归并排序示例 7 2011/10/25