744


:

Sequence <A1', A2', ...An'> of numbers

:

Permutation of numbers <A1',A2',...An'>

:

Merge Sort (Recursive sorting)

  1. IF n=1, DONE //already sorted
  2. Recursively sort 
    1. A[1,...(n/2)]              AND
    2. A[(n/2)+1,...n]
  3. Merge two sorted list (Subroutine)

 

:

 

aka Two figures algorithm.

Merge sort is a recursive algorithm. It works as follows.

  1. Divides the array into two part and then merge them back. 
  2. Each half will again perform #1 (until there are only two elements remaining)

 

We have 1+log n levels and n leaves. For each level its Cn of work.

So T(n) = (1+logn)*Cn = Θ (n Log n) 

 

Merge sort needs  Θ (n) auxiliary space.

We also have In-place Merge Sort which will not take more space but time complexity is very high.

 

:

O(n log(n))

:

O(n log(n))