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.