What is Merge Sort?

• Merge Sort is an algorithm that sorts an array by dividing it in half, sorting each part, and then merging them.

• Divide: Split the array into two parts.

• Conquer: Individually sort each part.

• Merge: Combine the sorted parts into a single array.

• Worst-case time complexity: O(nlog n) - Merge Sort takes time proportional to the logarithm of the number of elements, multiplied by the number of elements.

1. Divide step: Split the list into two parts. This process continues recursively.

2. Conquer step: Individually sort each part.

3. Merge step: Merge the sorted subarrays into one array.

4. Sorted completion: All subarrays are merged to form a completely sorted array.

• Recursive approach: Breaks down problems into smaller problems and solves them recursively.

• Efficiency: The divide and conquer method is highly efficient for large-scale data.