Given an array arr[], its starting position l and its ending position h.
The task is to sort the array using merge sort algorithm.
Input: arr[] = {12, 11, 13, 5, 6, 7}
Output: 5,6,7,11,12,13
Input: arr[] = {38, 27, 43, 3, 9, 82, 10}
Output: 3,9,10,27,38,43,82
Solutions
Method 1: Merge Sort
The Merge Sort algorithm is a Divide and Conquer sorting algorithm.
In this algorithm, we continuously split the array in half until it cannot be further divided (the array becomes empty or has only one element).
The "merge" function is recursively invoked on each of the halves.
The "merge" function is the process of taking two smaller sorted arrays and combining them in sorting order.
Complexity
The time complexity of this solution is O(n log n) and space complexity is O(n).