Implement a function to sort an array using the Merge Sort algorithm. The function should return the sorted array. Example 1: Input: arr = [38, 27, 43, 3, 9, 82, 10] Output: [3, 9, 10, 27, 38, 43, 82] Example 2: Input: arr = [5, 1, 4, 2, 8] Output: [1, 2, 4, 5, 8] Constraints: - 1 <= arr.length <= 10^6 - -10^6 <= arr[i] <= 10^6.

``` def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): sorted_arr = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: sorted_arr.append(left[i]) i += 1 else: sorted_arr.append(right[j]) j += 1 sorted_arr.extend(left[i:]) sorted_arr.extend(right[j:]) return sorted_arr ```