﻿==================================================
1. MERGE SORT
==================================================

ALGORITHM:
1. Divide the array into two halves using mid = (low + high) / 2.
2. Recursively sort the left half.
3. Recursively sort the right half.
4. Create temporary arrays L[] and R[].
5. Compare elements and copy the smaller element into the original array.
6. Copy the remaining elements.
7. Repeat until the complete array is sorted.

RECURRENCE RELATION:
T(n) = 2T(n/2) + O(n)

RECURSIVE ANALYSIS:
T(n) = 2T(n/2) + cn
T(n) = 4T(n/4) + 2cn
T(n) = 8T(n/8) + 3cn

General:
T(n) = 2^k T(n/2^k) + kcn

At k = log2(n):
T(n) = O(n log n)

TIME COMPLEXITY:
Best Case    : O(n log n)
Average Case : O(n log n)
Worst Case   : O(n log n)
Space        : O(n)