Sequence <A1', A2', ...An'> of numbers
Permutation of numbers <A1',A2',...An'>
Merge Sort (Recursive sorting)
- IF n=1, DONE //already sorted
- Recursively sort
- A[1,...(n/2)] AND
- Merge two sorted list (Subroutine)
Merge sort is a recursive algorithm. It works as follows.
- Divides the array into two part and then merge them back.
- Each half will again perform #1 (until there are only two elements remaining)