To implement a program that sort an array of elements using Merge Sort.
Merge Sort is a popular sorting algorithm that uses the divide and conquer approach to sort an array. The Merge Sort algorithm works by dividing the array into two halves repeatedly until each sub-array contains only one element. Then it merges the sub-arrays in a sorted manner until the original array is sorted.
The program starts with the "mergeSort" function, which takes three arguments - the array to be sorted (arr), the starting index of the array (l), and the ending index of the array (r). If the starting index is less than the ending index, it calculates the middle index m of the array and recursively calls "mergeSort" on the left half of the array and the right half of the array. This recursive call continues until each sub-array contains only one element.
Once the sub-arrays are sorted, the "merge" function is called to merge them. The "merge" function takes four arguments - the array to be sorted (arr), the starting index of the left sub-array (l), the ending index of the left sub-array and the starting index of the right sub-array (m), and the ending index of the right sub-array (r).
The "merge" function creates two sub-arrays - "L" and "R" - to store the left and right halves of the original array. It then iterates over these sub-arrays, comparing the elements and merging them into a new sorted array. Once one of the sub-arrays has been completely merged, the function appends the remaining elements of the other sub-array to the end of the sorted array.