Merge Sort.ppt

Merge Sort * Analysis of Merge-Sort The height h of the merge-sort tree is O(log n) at each recursive call we divide in half the sequence, The overall amount or work done at the nodes of depth i is O(n) we partition and merge 2i sequences of size n/2i we make 2i+1 recursive calls Thus, the total running time of merge-sort is O(n log n) depth #seqs size 0 1 n 1 2 n/2 i 2i n/2i … … … Merge Sort * Summary of Sorting Algorithms Algorithm Time Notes selection-sort O(n2) slow in-place for small data sets ( 1K) insertion-sort O(n2) slow in-place for small data sets ( 1K) heap-sort O(n log n) fast in-place for large data sets (1K — 1M) merge-sort O(n log n) fast sequential data access for huge data sets ( 1M) Merge Sort * * * * * Merge Sort ? 2004 Goodrich, Tamassia ? 2004 Goodrich, Tamassia Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort Merge Sort * Merge Sort 7 2 ? 9 4 ? 2 4 7 9 7 ? 2 ? 2 7 9 ? 4 ? 4 9 7 ? 7 2 ? 2 9 ? 9 4 ? 4 Merge Sort * Divide-and-Conquer (§ 10.1.1) Divide-and-conquer (分治演算法) is a general algorithm design paradigm: Divide: divide the input data S in two disjoint subsets S1 and S2 Conquer: solve the subproblems associated with S1 and S2 Combine: combine the solutions for S1 and S2 into a solution for S The base case for the recursion are subproblems of size 0 or 1 Merge-sort is a sorting algorithm based on the divide-and-conquer paradigm Like heap-sort It uses a comparator It has O(n log n) running time Unlike heap-sort It does not use an auxiliary priority queue It accesses data in a sequential manner (suitable to sort data on a disk) External sort 化整為零 各個擊破 Merge Sort Merge sort A divide and conquer algorithm Invented by John von Neumann in 1945 Merge Sort * 約翰·馮·紐曼（John von Neumann，1903年12月28日－1957年2月8日），出生於匈牙利的美國籍猶太人數學家，現代電腦創始人之一。他在電腦科學、經濟、物理學中的量子力學及幾乎所有數學領域都作過重大貢獻，被譽為「電腦之父」。(圖及說明摘自維基百科) Merge Sort * Merge-Sort (§ 10.1) Merge-sort on an input seque