##### Merge sort algorithm, analysis and problems
Content covered:

Merge Sort: Merge sort is a sorting technique based on divide and conquer technique. Merge sort first divides the array into equal halves and then combines them in a sorted manner.
MERGE-SORT (Apr)

1.     IF p < r                                                    // Check for base case
2.         THEN q = FLOOR[(p + r)/2]                 // Divide step
3.                 MERGE (A, pq)                          // Conquer step.
4.                 MERGE (A, q + 1, r)                     // Conquer step.
5.                 MERGE (A, pqr)                       // Conquer step.

MERGE (Apqr )

1.      n1 ← q − p + 1
2.      n2 ← r − q
3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4.      FOR i ← 1 TO n1
5.            DO L[i] ← A[p + i − 1]
6.      FOR j ← 1 TO n2
7.            DO R[j] ← A[q + j ]
8.      L[n1 + 1] ← ∞
9.      R[n2 + 1] ← ∞
10.    ← 1
11.    j ← 1
12.    FOR k ← p TO r
13.         DO IF L[i ] ≤ R[ j]
14.                THEN A[k] ← L[i]
15.                        i ← i + 1
16.                ELSE A[k] ← R[j]
17.                        j ← j + 1

Time Complexity:
Best Case - O(n logn)
Average Case - O(n logn)
Worst Case - O(n logn)

Note- Merge Sort is a stable sort.