UNIT 5C Merge Sort

UNIT 5C

Merge Sort

15110 Principles of Computing, Carnegie

Mellon University

1

Divide and Conquer

?

In computation:

¨C

¨C

¨C

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