Time Complexity of Merge Sort

Merge sort recursively splits the array in half and merges sorted halves.

Solve the recurrence $T(n)=2T(n/2)+O(n)$.

1. 1. Set up the recurrence

   Merge sort splits the array into two halves, recursively sorts each, and merges them in linear time.

   $$T(n)=2T(n/2)+O(n)$$

2. 2. Solve the recurrence

   This recurrence falls under the Master theorem case where the work at each of the $\log n$ levels is $O(n)$, giving a total of $O(n\log n)$.

Answer: O(n log n)