Designing Algorithms

Insertion sort is an incremental algorithm.

Sorting via divide and conquer : (using recursion)

• Divide: big problems into several small problems
• Conquer: solve "easy" small problems
• Combine: put small solutions together

Merge Sort ( divide and conquer)

Recursively : Divide list in half
                  : Sort if only one item in list
                  : Merge

Merging two sorted lists (cards perhaps) of combined size n takes n steps.

Routines:

Merge-Sort ( A, p, r ) sorts A[p...r]

Merge ( A, p, q, r) merges A[p...r] & A[q+1...r] in sorted order.

Note: Dividing recursively works best when n = 2^k

Merge-Sort ( A, p, r )
if p < r
   then q ¬  ë( p + r ) / 2 û // closest integer to the mid-point
   Merge-Sort ( A, p, r )
   Merge-Sort ( A, q + 1, r )
   Merge ( A, p, q, r )

T (n ) = Q (1) if n = 1
          = 2T ( n / 2 ) + Q (n) if n > 1

T (n)  = Q (n lg n)