上游充通大学 Mergesort SHANGHAI JIAO TONG UNIVERSITY ©Mergesort.. Divide array into two halves. Recursively sort each half. Jon von Neumann(1945) Merge two halves to make sorted whole. A G R 工TH MS A G R divide 0(1) A G L R HI M S T sort 2T(n/2) A merge O(n)6 Mergesort Mergesort. • Divide array into two halves. • Recursively sort each half. • Merge two halves to make sorted whole. merge sort divide A L G O R I T H M S A L G O R I T H M S A G L O R H I M S T A G H I L M O R S T Jon von Neumann (1945) O(n) 2T(n/2) O(1)