Merge Sort
Divide and Conquer.
1. Divide the array recursively till 2.
2. Sort these two elements.
3. Merge these elements.
Complexity: nlogn
Reason: Creates a complete binary tree with n leaves. Height - logn. So, compare (during merge) n elements, logn times.
For formal proof, go through the video.