Input:

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

Output:

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

Pseudocode:

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)

 

Description:

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)

 

Running Time:

O(n)

Worst Case:

O(n log(n))

Avarage Case:

O(n log(n))