UNIT 5C Merge Sort

UNIT 5C Merge Sort

15110 Principles of Computing, Carnegie Mellon University

1

Divide and Conquer

? In computation:

? Divide the problem into "simpler" versions of itself.

? Conquer each problem using the same process (usually recursively).

? Combine the results of the "simpler" versions to form your final solution.

Examples:

Towers of Hanoi, Fractals,

Binary Search,

Merge Sort,

Quicksort,

and many, many more

4

Divide

Group of 8 Groups of 4 Groups of 2 Groups of 1

Now each "group" is (trivially) sorted!

3

Conquer (merge sorted lists)

4

Conquer (merge sorted lists)

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download