What is Merge Sort?

Merge Sort is a divide and conquer sorting algorithm.

It divides the array into halves, sorts them, and merges them.

Steps

1. Divide array into two halves
2. Recursively sort both halves
3. Merge the sorted halves

Time Complexity

Merge Sort runs in O(n log n) time.