🚀 Day 27 with Data Structures and Algorithms (DSA): Merge Sorting using Recursion 📊

Today on 27th day marked a significant exploration into the realm of sorting algorithms as we delved into the intricacies of Merge Sort and its application in solving real-world problems. Let's unravel the journey of understanding, implementing, and leveraging the power of Merge Sort.

Merge Sort:

Merge Sort is a popular sorting algorithm that follows the Divide and Conquer strategy to efficiently sort an array or a list of elements. It was devised by John von Neumann in 1945 and is known for its stability and predictable runtime.

Algorithm Steps:

1. Divide: The unsorted list is divided into two equal halves until each sublist contains only one element.
2. Conquer: The individual elements are then merged in a sorted manner, creating new sorted sublists.
3. Combine: The merging process continues until a single sorted list is obtained.

Advantages of Merge Sort:

1. Stability: Merge Sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements in the sorted output.
2. Predictable Performance: It guarantees a consistent O(n log n) time complexity, making it efficient for large datasets. This ensures that the algorithm performs well even as the size of the input increases.
3. No Worst-Case Scenario: Unlike some other sorting algorithms, Merge Sort doesn't have a worst-case scenario. Its time complexity remains O(n log n) regardless of the input distribution.
4. External Sorting: Merge Sort is suitable for external sorting scenarios where data is too large to fit into memory. The divide-and-conquer approach allows it to efficiently handle large datasets by dividing them into manageable chunks.
5. Parallelization Potential: Merge Sort can be easily parallelized, taking advantage of multiple processors or cores. Each subproblem of merging can be assigned to different processors, enhancing its performance.

Problems :

1. Merge Sort :-- First Approach :

Time Complexity: The time complexity of the Merge Sort algorithm implemented in this code is O(n log n), where 'n' is the number of elements in the array. .

Space Complexity: The space complexity is O(n) due to the additional space required for the temporary arrays used in the merging process.

2. Merge Sort :-- Second Approach :